邝斌的ACM模板（新）

上海大学 ACM 模板 by kuangbin

1 / 173 ACM 模板 kuangbin

字符串处理 ............................................................................................................................... 2

1、KMP 算法 .................................................................................................................... 2

2、扩展 KMP .................................................................................................................... 5

3、Manacher 最长回文子串 ........................................................................................... 6

4、AC 自动机 ................................................................................................................... 7

5、后缀数组 ..................................................................................................................... 9

4、求逆元 ....................................................................................................................... 20

5、模线性方程组 ........................................................................................................... 20

6、随机素数测试和大数分解(POJ 1811) ..................................................................... 21

7、欧拉函数 ................................................................................................................... 24

8、高斯消元（浮点数） ............................................................................................... 25

9、FFT ............................................................................................................................. 26

10、高斯消元法求方程组的解 ..................................................................................... 29

11、 整数拆分 ............................................................................................................... 34

12、求 A^B 的约数之和对 MOD 取模 .......................................................................... 36

13、莫比乌斯反演 ......................................................................................................... 37

3、树链剖分 ................................................................................................................... 45

4、伸展树（splay tree） ............................................................................................... 50

5、动态树 ....................................................................................................................... 55

6、主席树 ....................................................................................................................... 60

7、Treap.......................................................................................................................... 70

图论......................................................................................................................................... 75

1、最短路 ....................................................................................................................... 75

2、最小生成树 ............................................................................................................... 79

3、次小生成树 ............................................................................................................... 80

4、有向图的强连通分量 ............................................................................................... 81

11、生成树计数 ............................................................................................................. 98

11、二分图多重匹配 ................................................................................................... 101

12、KM 算法（二分图最大权匹配） ........................................................................ 102

13、最大流 ................................................................................................................... 103

14、最小费用最大流 ................................................................................................... 109

15、2-SAT ...................................................................................................................... 110

16、曼哈顿最小生成树 ............................................................................................... 114

17、一般图匹配带花树 ............................................................................................... 117

18、LCA ........................................................................................................................ 120

19、欧拉路 ................................................................................................................... 126

上海大学 ACM 模板 by kuangbin

2 / 173 ACM 模板 kuangbin

6、三点求圆心坐标（三角形外心） ......................................................................... 149

7、求两圆相交的面积 ................................................................................................. 150

8、Pick 公式 ................................................................................................................. 150

动态规划 ............................................................................................................................... 150

1、最长上升子序列 O(nlogn) ...................................................................................... 150

搜索....................................................................................................................................... 151

其他....................................................................................................................................... 156

1、高精度 ..................................................................................................................... 156

2、完全高精度 ............................................................................................................. 158

3、strtok 和 sscanf 结合输入 ...................................................................................... 163

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的自身匹配）

*/

void kmp_pre(char x[],int m,int next[])

{

int i,j;

j=next[0]=-1;

}

/*

* kmpNext[]的意思：next'[i]=next[next[...[next[i]]]] (直到next'[i]<0或者

x[next'[i]]!=x[i])

* 这样的预处理可以快一些

*/

void preKMP(char x[],int m,int kmpNext[])

{

int i,j;

j=kmpNext[0]=-1;

上海大学 ACM 模板 by kuangbin

3 / 173 ACM 模板 kuangbin

}

/*

* 返回x在y中出现的次数，可以重叠

{//x是模式串，y是主串

int i,j;

int ans=0;

//preKMP(x,m,next);

kmp_pre(x,m,next);

i=j=0;

while(i<n)

{

while(-1!=j && y[i]!=x[j])j=next[j];

i++;j++;

return ans;

}

经典题目：POJ 3167

/*

* POJ 3167 Cow Patterns

* 模式串可以浮动的模式匹配问题

* 给出模式串的相对大小，需要找出模式串匹配次数和位置

* 比如说模式串：1，4，4，2，3，1 而主串：5,6,2,10,10,7,3,2,9

* 那么2,10,10,7,3,2就是匹配的

#include <algorithm>

#include <vector>

using namespace std;

const int MAXN=100010;

const int MAXM=25010;

int a[MAXN];

int b[MAXN];

int n,m,s;

int as[MAXN][30];

int bs[MAXM][30];

上海大学 ACM 模板 by kuangbin

4 / 173 ACM 模板 kuangbin

else

{

for(int j=1;j<=25;j++)as[i][j]=as[i-1][j];

for(int i=0;i<m;i++)

{

if(i==0)

{

for(int j=1;j<=25;j++)bs[i][j]=0;

}

else

{

for(int j=1;j<=25;j++)bs[i][j]=bs[i-1][j];

}

int i,j;

j=next[0]=-1;

上海大学 ACM 模板 by kuangbin

5 / 173 ACM 模板 kuangbin

for(int k=1;k<a[i];k++)

{

if(i-j>0)t11+=as[i][k]-as[i-j-1][k];

else t12=as[i][a[i]];

for(int k=1;k<b[j];k++)

{

t21+=bs[j][k];

}

t22=bs[j][b[j]];

if(j==-1 || (t11==t21&&t12==t22))

{

i++;j++;

else j=next[j];

}