字符串知识点复习
KMP
可爱的初级字符串算法。是某钻石教练会讲的算法。复杂度线性。
前缀数组（nxt）
定义： 代表 子串
最长的相等的真前缀与真后缀的长度（字符串下标从
开始）。规定 。
可以这样理解：
的意思是将字符串整体向右挪动，当 到达
的位置时，第一次出现前缀与原位置完全吻合。这样，当 位失配时，我们只需要将 挪到 的位置，保证前 位都是正确的，更改第 位。
可爱的实现
1
2
3
4
5
6
7
8
| void make(){
for(int i=2;i<=lx;i++){
int k=nxt[i-1];
while(k&&x[k+1]!=x[i]) k=nxt[k];
if(x[k+1]==x[i]) k++;
nxt[i]=k;
}
}
|
匹配操作
给定一个文本串和一个模式串，我们尝试找到并展示模式串在文本串中的所有出现。
可爱的实现
1
2
3
4
5
6
7
8
| void work(){
int tx=0;
for(int i=1;i<=ly;i++){
while(tx&&x[tx+1]!=y[i]) tx=nxt[tx];
if(x[tx+1] == y[i]) tx++;
if(tx == lx) printf("%d\n",i-lx+1);
}
}
|
Manacher
高妙的回文串检索算法。复杂度线性。思想是减少已知的判断，类似
KMP。
小但神奇的点：首先先在任意两个字符之间以及头尾字符两侧插入一个#。然后，你将惊奇地发现：原串的回文串直径恰好是新串中回文串的半径（上取整）减一。人类智慧
高妙的实现
1
2
3
4
5
6
7
8
9
10
11
12
| void manacher(){
int l=1,r=1,L=2*ls+1;
for(int i=2;i<=L;i++){
int k=r<i?1:min(len[l+r-i],r-i+1);
while(1<=i-k&&i+k<=L&&s[i-k]==s[i+k]) k++;
len[i]=k--;
if(i+k>r){
r=i+k;
l=i-k;
}
}
}
|
SA
可以在
时间复杂度内求出一个字符串的每一个后缀的字典序的排名。用到了基数排序和倍增的思想。每次处理出每一个位置向后延伸一定长度的字符串的排名，借助上一次的处理结果可以双关键字排序，从而不断进行更新。
算法流程
准备四个数组：，其中
是第一关键字的值， 是第二关键字的排序，即 代表第二关键字第 小的下标。
是统计某一个值的出现次数（用于基数排序）， 用来暂时存储当前答案，即当前排名为
的后缀下标。
初始化：
- 统计最开始的 。直接按照字符大小赋值即可。顺便统计
。
- 对 数组求前缀和。
- 统计最开始的 。简单来说就是
sa[c[x[i]]--]=i。
对于每一次更新，记当前后缀长度为 ：
- 首先根据上一次的 处理出
数组。
- 对于后 位，由于第
位不存在，第二关键字为空，可以视为最小，直接存在 中。
- 对于其他位 ，它们的第二关键字应该对应于上一次的
数组中的 的位置，即如果 ，那么 将成为 的第二关键字。
- 按照
顺序遍历，则先遍历到的第二关键字一定更小；记一个下标 不断向 中添加新元素即可。
- 然后更新 。首先清空 ，然后借助 数组更新 ，再对 求前缀和，如刚才方法更新 。
- 最后更新 数组。暂时使用闲置的
数组存储之前的 。根据刚刚处理出的 ，顺序遍历
数组，初始设置
num=1，如果发现第一关键字或第二关键字有变动，就执行++num。当
时，意味着所有后缀的第一关键字值都不相同，此时就可以跳出循环了。
优秀的实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| void SA(){
for(int i=1;i<=n;i++) x[i]=s[i],c[x[i]]++;
for(int i=2;i<=m;i++) c[i]+=c[i-1];
for(int i=n;i>=1;i--) sa[c[x[i]]--]=i;
for(int k=1;k<=n;k<<=1){
int num=0;
for(int i=n-k+1;i<=n;i++) y[++num]=i;
for(int i=1;i<=n;i++) if(sa[i]-k>0) y[++num]=sa[i]-k;
for(int i=1;i<=m;i++) c[i]=0;
for(int i=1;i<=n;i++) c[x[i]]++;
for(int i=2;i<=m;i++) c[i]+=c[i-1];
for(int i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i];
swap(x,y);
num=1;
x[sa[1]]=1;
for(int i=2;i<=n;i++){
if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]) x[sa[i]]=num;
else x[sa[i]]=++num;
}
if(num==n) break;
m=num;
}
}
|