邝斌的ACM模板

改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.01/95改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.02/95字符串处理...........................................31、KMP算法.....................................32、扩展KMP......................................43、Manacher最长回文子串........................54、AC自动机....................................55、后缀数组.....................................76、后缀自动机...................................97、字符串HASH..................................10数学................................................101、素数........................................102、素数筛选和合数分解..........................123、扩展欧几里得算法（求ax+by=gcd的解以及逆元素）124、求逆元......................................125、模线性方程组................................126、随机素数测试和大数分解(POJ1811)............137、欧拉函数....................................148、高斯消元（浮点数）..........................159、FFT.........................................1610、高斯消元法求方程组的解.....................1711、整数拆分..................................2012、求A^B的约数之和对MOD取模.................2113、莫比乌斯反演...............................2214、Baby-StepGiant-Step.......................2315、自适应simpson积分.........................23相关公式.......................................23数据结构............................................241、划分树......................................242、RMQ.........................................253、树链剖分....................................264、伸展树（splaytree）........................295、动态树......................................316、主席树......................................347、Treap.......................................40图论................................................421、最短路......................................422、最小生成树..................................443、次小生成树..................................444、有向图的强连通分量..........................455、图的割点、桥和双连通分支的基本概念..........466、割点与桥.....................................477、边双连通分支.................................488、点双连通分支.................................509、最小树形图...................................5110、二分图匹配..................................5211、生成树计数..................................5411、二分图多重匹配..............................5612、KM算法（二分图最大权匹配）.................5613、最大流......................................5714、最小费用最大流..............................6015、2-SAT.......................................6116、曼哈顿最小生成树............................6417、一般图匹配带花树............................6518、LCA.........................................6719、欧拉路......................................70计算几何.............................................731、基本函数.....................................732、凸包1383、平面最近点对（HDU1007）1394、旋转卡壳1405、半平面交1466、三点求圆心坐标（三角形外心）1497、求两圆相交的面积1508、Pick公式150动态规划1501、最长上升子序列O(nlogn)150搜索1511、DancingLinks151其他1561、高精度1562、完全高精度1583、strtok和sscanf结合输入1634、解决爆栈，手动加栈1635、STL1636、输入输出外挂1657、莫队算法1668、VIM配置172改版者言：此版本是由2013-11-8月上传的pdf文档改版的。非2013-9-27版本的改版。做了写简单处理内部代码没动过但是：本文的格式发生改动部分文字的格式出现问题一些表达式已无法辨认代码中少量大括号错位目录无法正常使用，改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.03/95字符串处理1、KMP算法/**next[]的含义：x[i-next[i]...i-1]=x[0...next[i]-1]*next[i]为满足x[i-z...i-1]=x[0...z-1]的最大z值（就是x的自身匹配）*/voidkmp_pre(charx[],intm,intnext[]){inti,j;j=next[0]=-1;i=0;while(im){while(-1!=j&&x[i]!=x[j])j=next[j];next[++i]=++j;}}/**kmpNext[]的意思：next'[i]=next[next[...[next[i]]]](直到next'[i]0或者x[next'[i]]!=x[i])*这样的预处理可以快一些*/voidpreKMP(charx[],intm,intkmpNext[]){inti,j;j=kmpNext[0]=-1;i=0;while(im){while(-1!=j&&x[i]!=x[j])j=kmpNext[j];if(x[++i]==x[++j])kmpNext[i]=kmpNext[j];elsekmpNext[i]=j;}}/**返回x在y中出现的次数，可以重叠*/intnext[10010];intKMP_Count(charx[],intm,chary[],intn){//x是模式串，y是主串inti,j;intans=0;//preKMP(x,m,next);kmp_pre(x,m,next);i=j=0;while(in){while(-1!=j&&y[i]!=x[j])j=next[j];i++;j++;if(j=m){ans++;j=next[j];}}returnans;}经典题目：POJ3167/**POJ3167CowPatterns*模式串可以浮动的模式匹配问题*给出模式串的相对大小，需要找出模式串匹配次数和位置*比如说模式串：1，4，4，2，3，1而主串：5,6,2,10,10,7,3,2,9*那么2,10,10,7,3,2就是匹配的**统计比当前数小，和于当前数相等的，然后进行kmp*/#includeiostream#includestdio.h#includestring.h#includealgorithm#includevectorusingnamespacestd;constintMAXN=100010;constintMAXM=25010;inta[MAXN];intb[MAXN];intn,m,s;intas[MAXN][30];intbs[MAXM][30];voidinit(){for(inti=0;in;i++)if(i==0){for(intj=1;j=25;j++)as[i][j]=0;}else{for(intj=1;j=25;j++)as[i][j]=as[i-1][j];}as[i][a[i]]++;}for(inti=0;im;i++){if(i==0){for(intj=1;j=25;j++)bs[i][j]=0;改版人：小Angel，初稿2016-7-27，当前2016-7-28，版本1.04/95}else{for(intj=1;j=25;j++)bs[i][j]=bs[i-1][j];}bs[i][b[i]]++;}}intnext[MAXM];voidkmp_pre(){inti,j;j=next[0]=-1;i=0;while(im){intt11=0,t12=0,t21=0,t22=0;for(intk=1;kb[i];k++){if(i-j0)t11+=bs[i][k]-bs[i-j-1][k];elset11+=bs[i][k];}if(i-j0)t12=bs[i][b[i]]-bs[i-j-1][b[i]];elset12=bs[i][b[i]];for(intk=1;kb[j];k++){t21+=bs[j][k];}t22=bs[j][b[j]];if(j==-1||(t11==t21&&t12==t22)){next[++i]=++j;}elsej=next[j];}}vectorintans;voidkmp(){ans.clear();inti,j;kmp_pre();i=j=0;while(in){intt11=0,t12=0,t21=0,t22=0;for(intk=1;ka[i];k++){if(i-j0)t11+=as[i][k]-as[i-j-1][k];elset11+=as[i][k];}if(i-j0)t12=as[i][a[i]]-as[i-j-1][a[i]];elset12=as[i][a[i]];for(intk=1;kb[j];k++){t21+=bs[j][k];}t22=bs[j][b[j]];if(j==-1||(t11==t21&&t12==