OI模板梳理

OI模板梳理

明天自招考试!
花点时间把一些老博客上的一些板子转移过来,顺便也复习一下。
不要问我为什么有封面……

图片来自unsplash.com

一 图论

1 最短路

1-1 Dijkstra

Dijkstra 的贪心策略正确当且仅当图上不存在负权环。

Dijkstra 认为:一个点只会被某些特定的点“松弛”,因为如果从其它点转移,最短路径要么变长,要么不变,而绝不可能变短;Dijkstra 每次在做的是就是找到这样的一个“特定的点”,即当前最短路径长度最小的那个点。

这是一个很贪心的策略,因此其成立是有条件的,即图上没有负权环。注意,一条无向的负权边也是负权环。

堆优化 Dijkstra :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#define LL long long
const int CN = 1e5+5;
const LL INF = 0x3f3f3f3f3f3f3f2f;

class fs {public: int to,nxt; LL di;} E[CN * 51];
int hd[CN];

class DJ{
public: int id; LL v;
bool operator < (const DJ& a)const {return v > a.v;}
};
priority_queue<DJ> Q;
LL d[CN]; bool vis[CN];
LL SP(int s,int t){
memset(vis, 0, sizeof(vis)); memset(d, 0x3f, sizeof(d));
Q.push((DJ){s, d[s] = 0});
while(!Q.empty()){
int u = Q.top().id; Q.pop();
if(vis[u]) continue; vis[u] = true; // 必须在此处标记访问
for(int k = hd[u]; k; k = E[k].nxt){
int v = E[k].to;
if(d[v] > d[u] + E[k].di){
d[v] = d[u] + E[k].di;
if(!vis[v]) Q.push((DJ){v, d[v]}); // 不能在此处标记访问,因为先入队时该点不一定达到最优
}
}
}
return d[t] < INF ? d[t] : -1;
}

1-2 Floyd

1
2
3
4
5
int f[][];
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j] = min(f[i][j], f[i][k]+f[k][j]);

1-3 Bellman-Ford / SPFA

Has it dead?

出题人造数据当然要卡 SPFA ,但这也要考虑到历史的行程。众所周知,历史的行程可以被抽象成一串01串……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool ins[CP]; //  是否在队列中
int times[CP]; // times[i] : 节点i被松弛的次数
int d[CP]; // 保存单源最短路
bool spfa(int s){ // 返回有解(true)或无解(false)
memset(d,0x3f,sizeof(d));
memset(ins,false,sizeof(ins));
memset(times,0,sizeof(times));
queue<int>Q; Q.push(s); d[s]=0;
while(!Q.empty()){
int u=Q.front(); Q.pop(); ins[u]=false;
for(int k=hd[u]; k; k=E[k].nxt){
fs e=E[k];
if(d[u]+e.dist < d[e.to]){ // 松弛
d[e.to]=d[u]+e.dist;
if(!ins[e.to]){ // 不在队列中就入队
Q.push(e.to); ins[e.to]=true;
if(++times[e.to] == n) // 松弛了超过n次,存在负环
return false;
}
}
}
}
return true;
}

2 最小生成树

2-1 Kruskal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class edge{...}; 
class ufs{...}; // 并查集
edge E[];
ufs s;
int mst(){
int cnt=0,cst=0;
sort(E+1,E+m+1);
for(int k=1; cnt!=n-1 && k<=m; k++){ // 枚举所有边
if(s.find(E[k].from) == s.find(E[k].to)) continue;
s.fa[find(E[k].from)] = s.find(E[k].to);
cnt+=1; cst+=E[k].c;
}
return cst;
}

2-2 Prim

有点像DJ。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class fs{...}; // 边表
fs E[];
int dis[]; // dis[i] : 1~i的所有边中边权最小的那一个
bool vis[];
int prim(){
memset(dis,0x3f,sizeof(dis));
for(re int i=hd[1];i;i=E[i].nxt)
dis[E[i].to] = min(dis[E[i].to], E[i].c);
int cur=1,cst=0;
for(int i=1; i<n; i++){
int mn=INF;
vis[cur]=1;
for(int i=1;i<=n;++i) // 挑出最小的一个
if(!vis[i] && mn>dis[i])
mn=dis[cur=i];
cst+=mn;
for(re int i=hd[cur]; i ;i=E[i].nxt) // update
if(!vis[E[i].to] && dis[E[i].to]>E[i].c)
dis[E[i].to] = E[i].c;
}
return cst;
}

3 并查集

1
2
3
4
5
class DSU{
public: int fa[CN]; DSU() {for(int i = 1; i < CN; i++) fa[i] = i;}
int fd(int x) {return fa[x] ^ x ? fa[x] = fd(fa[x]) : x;}
bool mg(int x,int y) {x = fd(x), y = fd(y); return x ^ y ? fa[x] = y, 1 : 0;}
} D;

其它

以下内容请在本站搜索相应文章。
  • 树链剖分 \ LCA
  • 树的重心 \ 树的直径
  • 最大流 \ 最小费用最大流(二分图相关)
  • 强连通分量(缩点) \ 双连通分量
  • 倍增LCA
  • 二分图匹配(匈牙利)
  • k 短路问题(A* 寻路,请参阅这篇文章

二 数论

1 素数筛

Eratosthenes 筛法,此筛法非严格的线性。有关线性筛,请见另一篇博文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define LL long long
const int CN = 1e7+7;

bool isp[CN]; // 判断素数
LL prime[CN]; // 保存素数

void GetPrime(LL n){
memset(isp,true,sizeof(isp));
for(LL i=2;i<=n;i++){
if(isp[i]){
prime[++prime[0]] = i;
for(int k=2;i*k<=n;k++)
isp[i*k] = false;
}
}
}

2 分解质因数

试除法,复杂度$O(\sqrt{x})$。
注:一个数的质因数数量是$\log$级别。

1
2
3
4
5
6
7
8
9
10
11
12
13
#define LL long long
const int CN = 101;

int cnt = 0; long long p[CN],a[CN];

void Div(LL x){
for(LL i = 2; i * i <= x; i++){
if(x % i) continue;
p[++cnt] = i;
while(!(x % i)) {a[cnt]++; x /= i;}
}
if(x > 1) p[++cnt] = x,a[cnt] = 1;
}

3 高斯-约旦消元

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/*
解方程组:
a1x1 + a2x2 +...+ anxn = s1
b1x1 + b2x2 +...+ bnxn = s2
...
*/

#define DB double
const int CN = 110;

int n;
DB a[CN][CN];
/*
a[][] : 增广矩阵
a[][n+1] : 储存常数项
*/
DB dabs(DB x) {return x<0 ? x : -x;} // 绝对值

/*
高斯 - 约旦消元 :
通过加减消元,把原方程组化成
k1x1 = v1
k2x2 = v2
...
knxn = vn
的形式,再计算
*/
DB x[CN]; // 保存答案
bool gauss(){
for(int i=1;i<=n;i++){ // 枚举未知数
DB mx = a[i][i]; int p = i;
for(int j=i+1;j<=n;j++){ // 挑选未知数x[i]的最大系数
if(dabs(mx) < dabs(a[j][i]))
mx = a[p = j][i];
}
if(!mx) return false; // 无解
for(int j=1;j<=n+1;j++) // 行、行交换
swap(a[i][j], a[p][j]);
/*加减消元*/
for(int j=1;j<=n;j++){ // 枚举方程
if(j == i) continue;
for(int k=i+1;k<=n+1;k++){ // 枚举系数
a[j][k] -= a[i][k]*(a[j][i]/a[i][i]);
}
}
}
for(int i=1;i<=n;i++)
x[i] = a[i][n+1]/a[i][i]; // 保存解
return true;
}

4 扩展欧几里得算法

扩展欧几里得算法用于求解形如 $ax+by=c$ 的二元不定方程的整数解。根据裴蜀定理,该不定方程有解当且仅当 $(a,b)|c$。容易发现,若 $(x,y)$ 是解,则 $(x+kb, y-ka), k\in \mathbb{Z}$ 也是解。

代码:

1
2
3
4
5
6
7
8
9
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}
void exgcd(int a, int &x, int b, int &y){
if(!b) return (void)(x = 1, y = 0);
exgcd(b, x, a % b, y); int t = x; x = y, y = t - (a / b) * y;
}
bool solve(int a, int &x, int b, int &y, int c){
int g = gcd(a, b); if(c % g) return false;
return exgcd(a, x, b, y), c /= g, x *= c, y *= c, true;
}

5 类欧几里得算法

类欧几里得算法仅适用于处理斜率和截距非负的线段。当斜率为负时,需要通过对称变换使得斜率为正;当截距为负时,需要通过平移坐标轴使截距为正。

求解:

$$f(n,A,B,C)=\sum_{i=0}^n\left\lfloor \frac{Ai+B}{C} \right\rfloor$$

其中满足 $A,B,C \ge 0$。它的几何意义是:在第一象限内,一条斜率和截距非负的线段下方的整点的数量。

实数版:

1
2
3
4
5
6
7
8
#define LL long long
LL s2(LL n) {return n * (n + 1) / 2;}
LL f(LL n, LL a, LL b, LL c){
if(!a) return (b / c) * (n + 1);
if(a >= c || b >= c) return s2(n) * (a / c) + (n + 1) * (b / c) + f(n, a % c, b % c, c);
LL m = (a * n + b) / c;
return n * m - f(m - 1, c, c - b - 1, a);
}

取模版:

1
2
3
4
5
6
7
8
9
#define LL long long
const int P = 998244353;
int s2(LL n) {return (n * (n + 1) / 2) % P;}
int f(LL n, LL a, LL b, LL c){
if(!a) return (b / c) * (n + 1) % P;
if(a >= c || b >= c) return (s2(n) * (a / c) % P + (n + 1) * (b / c) % P + f(n, a % c, b % c, c)) % P;
LL m = (a * n + b) / c;
return (n * m % P - f(m - 1, c, c - b - 1, a) + P) % P;
}

其它

以下内容请在本站搜索相应文章。
  • 矩阵快速幂(矩阵加速递推)
  • lucas(组合数取模)
  • gcd(最大公约数) \ exgcd(关于其求解不定方程的模板,请参阅CRT&exCRT
  • 逆元
  • CRT & exCRT(同余方程组)

三 多项式

1 FFT / 快速傅里叶变换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const int CN = 1e5+5;
const double PI = 3.14159265358;

class Comp{
public: double x,y;
void init(double xx,double yy){x = xx, y = yy;}
Comp operator + (const Comp &a)const {Comp b; b.x = x + a.x; b.y = y + a.y; return b;}
Comp operator - (const Comp &a)const {Comp b; b.x = x - a.x; b.y = y - a.y; return b;}
Comp operator * (const Comp &a)const {Comp b; b.x = x * a.x - y * a.y; b.y = x * a.y + y * a.x; return b;}
};

int rev[CN << 2];
void change(Comp *t,int n){
for(int i = 0;i < n;i++) rev[i] = (rev[i >> 1] >> 1) + (i & 1) * (n >> 1);
for(int i = 0;i < n;i++) if(i < rev[i]) swap(t[i], t[ rev[i] ]);
}
void fft(Comp* t,int n,int tp){
change(t, n);
for(int l = 2;l <= n;l <<= 1){ // 长度
Comp wn; wn.init(cos(2 * PI / l), sin(2 * tp * PI / l));
for(int i = 0;i < n; i += l){ // 起点
Comp w; w.init(1, 0);
for(int j = i;j < i + l / 2;j++){
Comp u = t[j], v = w * t[j + l / 2];
t[j] = u + v; t[j + l / 2] = u - v;
w = w * wn;
}
}
}
if(tp == -1) for(int i = 0;i < n; i++) t[i].x /= n;
}

2 NTT / 快速数论变换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int rev[CN << 2];
void change(int *t,int n){
for(int i = 0;i < n;i++) rev[i] = (rev[i >> 1] >> 1) + (i & 1) * (n >> 1);
for(int i = 0;i < n;i++) if(i < rev[i]) swap(t[i], t[ rev[i] ]);
}
void ntt(int *t,int n,int tp){
int gi = qp(3, P - 2); change(t, n);
for(int l = 2;l <= n;l <<= 1){
int gn = qp(tp ? 3 : gi, (P - 1) / l), k = l >> 1;
for(int i = 0;i < n;i += l){
int g = 1;
for(int j = i;j < i + k;j++){
int u = t[j], v = (1ll * g * t[j + k]) % P;
t[j] = (u + v) % P, t[j + k] = (u - v + P) % P;
g = (1ll * g * gn) % P;
}
}
}
if(!tp){
gi = qp(n, P - 2);
for(int i = 0;i < n;i++) t[i] = (1ll * t[i] * gi) % P;
}
}

3 求逆 / 指对运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int c[CN << 2],lnb[CN << 2];
void inv(int *a,int *b,int n){
for(int i = 0;i < (n << 1);i++) b[i] = 0; memset(c, 0, sizeof(c));
b[0] = qp(a[0], P - 2);
for(int l = 2;l < (n << 1);l <<= 1){
for(int i = 0;i < l;i++) c[i] = a[i];
ntt(b, l << 1, 1); ntt(c, l << 1, 1);
for(int i = 0;i < (l << 1);i++) b[i] = (1ll * b[i] * (2 - 1ll * c[i] * b[i] % P) % P + P) % P;
ntt(b, l << 1, 0);
for(int i = l;i < (l << 1);i++) b[i] = 0;
}
}
void ln(int *a,int *b,int n){
inv(a, b, n);
memset(c, 0, sizeof(c));
for(int i = 0;i < n - 1;i++) c[i] = 1ll * (i + 1) * a[i + 1] % P;
int l = 1; while(l < (n << 1)) l <<= 1;
ntt(c, l, 1); ntt(b, l, 1);
for(int i = 0;i < l;i++) b[i] = 1ll * b[i] * c[i] % P;
ntt(b, l, 0);
for(int i = n - 1;i;i--){
int in = qp(i, P - 2);
b[i] = 1ll * in * b[i - 1] % P;
}
b[0] = 0; for(int i = n;i < l;i++) b[i] = 0;
}
void exp(int *a,int *b,int n){
for(int i = 1;i < (n << 1);i++) b[i] = 0; b[0] = 1;
for(int l = 2;l < (n << 1);l <<= 1){
ln(b, lnb, l);
for(int i = 0;i < l;i++) lnb[i] = (a[i] - lnb[i] + P) % P;
lnb[0]++;
ntt(lnb, l << 1, 1); ntt(b, l << 1, 1);
for(int i = 0;i < (l << 1);i++) b[i] = 1ll * b[i] * lnb[i] % P;
ntt(b, l << 1, 0);
for(int i = l;i < (l << 1);i++) b[i] = 0;
}
for(int i = n;i < (n << 1);i++) b[i] = 0;
}

4 任意模数卷积

拆系数fft,细节参考毛啸(myy)的论文。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#define LDB long double
#define LL long long

const LDB PI = acos(-1.0);

class comp{
public: LDB x, y;
void init(LDB xx,LDB yy) {x = xx, y = yy;}
comp operator + (comp a) {comp c; c.init(x + a.x, y + a.y); return c;}
comp operator - (comp a) {comp c; c.init(x - a.x, y - a.y); return c;}
comp operator * (comp a) {comp c; c.init(x * a.x - y * a.y, x * a.y + y * a.x); return c;}
};
comp conj(comp a) {comp c; c.init(a.x, -a.y); return c;}
comp cm(LDB i,LDB j) {comp c; c.init(i, j); return c;}

int rev[CN << 2];
void change(comp *t, int n){
for(int i = 0;i < n;i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (n >> 1));
for(int i = 0;i < n;i++) if(i < rev[i]) swap(t[i], t[ rev[i] ]);
}
void fft(comp *t, int n, int tp){
change(t, n);
for(int l = 2;l <= n;l <<= 1){
comp wn; wn.init(cos(2 * PI / l), sin(2 * tp * PI / l));
int k = l >> 1;
for(int i = 0;i < n;i += l){
comp w; w.init(1, 0);
for(int j = i;j < i + k;j++){
comp u = t[j], v = w * t[j + k];
t[j] = u + v; t[j + k] = u - v;
w = w * wn;
}
}
}
if(tp == -1) for(int i = 0;i < n;i++) t[i].x /= n, t[i].y /= n;
}

int n,m; LL a[CN],b[CN];

comp fa[CN << 2],fb[CN << 2],d1[CN << 2],d2[CN << 2],d3[CN << 2],d4[CN << 2];
void conv(){
int l = 1; while(l < (n << 1) || l < (m << 1)) l <<= 1;

int bit = (1 << 15) - 1;
for(int i = 0;i < n;i++) fa[i].init(a[i] & bit, a[i] >> 15); // r k
for(int i = 0;i < m;i++) fb[i].init(b[i] & bit, b[i] >> 15); // _r _k
fft(fa, l, 1); fft(fb, l, 1);

for(int i = 0;i < l;i++){
int j = (l - 1) & (l - i);
comp r,k,_r,_k;
r = (fa[i] + conj(fa[j])) * cm(0.5, 0);
k = (fa[i] - conj(fa[j])) * cm(0, -0.5);
_r = (fb[i] + conj(fb[j])) * cm(0.5, 0);
_k = (fb[i] - conj(fb[j])) * cm(0, -0.5);

d1[i] = k * _k; d2[i] = _k * r; d3[i] = k * _r; d4[i] = r * _r;
}

for(int i = 0;i < l;i++) fa[i] = d1[i] + d2[i] * cm(0, 1);
for(int i = 0;i < l;i++) fb[i] = d3[i] + d4[i] * cm(0, 1);
fft(fa, l, -1); fft(fb, l, -1);

for(int i = 0;i < l;i++){
LL A = 1ll * (fa[i].x + 0.5), B = 1ll * (fa[i].y + 0.5),
C = 1ll * (fb[i].x + 0.5), D = 1ll * (fb[i].y + 0.5);
A = ((A % p) << 30) % p;
B = (((B + C) % p) << 15) % p;
D %= p;
a[i] = (A + B + D) % p;
}
}

四 字符串

1 KMP

有关 KMP 的总结请参见KMP学习笔记

1
2
3
4
5
6
7
8
9
10
int k = 0; nxt[1] = 0, nxt[0] = -1;
for(int i = 2; i <= m; i++){
while(k ^ -1 && t[k + 1] != t[i]) k = nxt[k];
nxt[i] = (k += 1);
}
k = 0;
for(int i = 1; i <= n; i++){
while(k ^ -1 && t[k + 1] != s[i]) k = nxt[k];
if((k += 1) == m) printf("%d", i - m + 1), puts("");
}

2 ACAM / AC 自动机

有关AC自动机的总结请参见KMP学习笔记

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int CN = 1e6 + 6;
class ACAM {
public: int son[CN][26], fail[CN], e[CN], idx; queue<int> Q;
void ins(char *s){ // 建立 tire 结构
int u = 0;
for(int i = 0; s[i]; i++){
if(!son[u][ s[i] - 'a' ]) son[u][ s[i] - 'a' ] = ++idx;
u = son[u][ s[i] - 'a' ];
}
e[u]++;
}
void bd(){ // 建立 fail 指针
for(int i = 0; i < 26; i++) if(son[0][i]) Q.push( son[0][i] );
while(!Q.empty()){
int u = Q.front(); Q.pop();
for(int i = 0; i < 26; i++)
if(son[u][i]) fail[ son[u][i] ] = son[ fail[u] ][i], Q.push(son[u][i]);
else son[u][i] = son[ fail[u] ][i];
}
}
} D;

3 SA / 后缀数组

后缀数组通过将后缀按字典序排序来获得一些优美的性质。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int rk[CN << 1], sa[CN], ht[CN];
/* rk[] 将 s[i:] 映射到排序后的排名 rk[i],有类似于离散化的作用 */
namespace SA{
int prk[CN << 1], id[CN], px[CN], cnt[CN];
void sort(char a[], int n){
int m = max(n, 300);
for(int i = 1; i <= n; i++) rk[i] = a[i];
for(int i = 1; i <= n; i++) cnt[ rk[i] ]++;
for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
for(int i = n; i; i--) sa[ cnt[ rk[i] ]-- ] = i; // id[i] = i
for(int w = 1; w < n; w <<= 1){
memset(cnt, 0, sizeof(cnt));
for(int i = 1; i <= n; i++) id[i] = sa[i];
for(int i = 1; i <= n; i++) cnt[ px[i] = rk[id[i] + w] ]++;
for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
for(int i = n; i; i--) sa[ cnt[ px[i] ]-- ] = id[i];
memset(cnt, 0, sizeof(cnt));
for(int i = 1; i <= n; i++) id[i] = sa[i];
for(int i = 1; i <= n; i++) cnt[ px[i] = rk[id[i]] ]++;
for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
for(int i = n; i; i--) sa[ cnt[ px[i] ]-- ] = id[i];
memcpy(prk, rk, sizeof(rk)), m = 0;
for(int i = 1; i <= n; i++)
if(prk[sa[i]] == prk[sa[i - 1]] && prk[sa[i] + w] == prk[sa[i - 1] + w])
rk[ sa[i] ] = m;
else rk[ sa[i] ] = ++m;
if(m == n) break;
}
for(int p = 0, i = 1; i <= n; i++){
if(p) p--;
while(a[i + p] == a[sa[rk[i] - 1] + p]) p++;
ht[ rk[i] ] = p;
}
}
}

4 SAM / 后缀自动机

后缀自动机可以将字符串的每一个子串双射在有向单词无环图(DAWG)上,从而获得一系列优美的性质。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int CN = 1e6 + 6;
class SAM{
public: int len[CN << 1], nxt[CN << 1], last, sz; int son[CN << 1][26];
SAM() {memset(son, 0, sizeof(son)), len[0] = 0, nxt[0] = -1, sz = 1, last = 0;}
void extend(int c){
int u = sz++, p = last;
last = u, len[u] = len[p] + 1;
while(p != -1 && !son[p][c]) son[p][c] = u, p = nxt[p];
if(p == -1) return (void)(nxt[u] = 0);
int d = son[p][c];
if(len[d] == len[p] + 1) return (void)(nxt[u] = d);
int v = sz++;
len[v] = len[p] + 1, nxt[v] = nxt[d], nxt[u] = nxt[d] = v;
memcpy(son[v], son[d], sizeof(son[d]));
while(p != -1 && son[p][c] == d) son[p][c] = v, p = nxt[p];
}
};

5 Manacher

众所周知,Manacher 是一种优雅的暴力。

1
2
3
4
5
6
7
8
9
10
11
12
cin >> (s + 1); n = strlen(s + 1); 

c[0] = '$', c[1] = '#';
for(int i = 1; i <= n; i++) c[i << 1] = s[i], c[i << 1 | 1] = '#';
n = n << 1 | 1, c[n + 1] = '.';

int k, i0 = 1; r[1] = 1;
for(int i = 2; i <= n; i++){
k = min(i0 + r[i0] - i, r[(i0 << 1) - i]);
while(c[i + k] == c[i - k]) k++;
r[i] = k; if(i + r[i] > i0 + r[i0]) i0 = i;
}
最近更新: 2020.9.1 添加了字符串算法。

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×