字符串算法
sdxjzsq
2020-03-06 23:17:33
## 背景
于3.5参加了成为ACM校队后的第一场集训，这次集训的内容是`KMP`算法，但运用`KMP`算法的核心题目[`Tavas and Malekas`](https://codeforces.com/problemset/problem/535/D)却没有解出来，因此重新温习了一下`KMP`算法和`字符串哈希`算法，计划将在本文加入~~`AC自动机`(已加入)~~和~~`后缀数组（SA）`算法(已加入)~~备忘。
咕掉的题目越来越多了...需要加把劲了！
flag:计划将`题目`与`核心算法/模板`分离，以简化页面，提高修改效率。
### 更新日志
3/26update:第七次训练题目:
3/22update:第六次训练题目:
C. CF710F String Set Queries(AC自动机)
F. HDU6096 String(AC自动机，待补)
G. CF963C Cutting Rectangle(AC自动机，待补)
H. CF1163D Mysterious Code(AC自动机，待补)
I. CF427D Match & Catch(后缀数组SA，待补)
J. UVA11107 Life Forms(后缀数组SA)
------------
3/19update:第五次训练题目:
F. CF1285D Dr. Evil Underscores(trie例1)
H. CF1207G Indie Album(AC自动机，待补)
I. POJ1204 Word Puzzles(AC自动机)
------------
3/15update:第四次训练的题目:
B. BZOJ3916 friends(字符串哈希例7)
C. CF1087E Vasya and Templates(待补)
D. UVA11019 Matrix Matcher(二维字符串哈希板子)
E. UVA12338 Anti-Rhyme Pairs(待补)
F. UVA10617 Again Palindrome(待补)
G. CF1183H Subsequences (hard version)(字符串DP)
H. CF1096D Easy Problem(待补)
I. [UVA1207 AGTC(最小编辑距离 外链)](https://www.luogu.com.cn/blog/xjzsq/solution-uva1207)
------------
3/12update:第三次训练的部分题目:（比赛过程中两题写好因为字符串哈希模数被卡...最后0提交...）
C. CF985F Isomorphic Strings（本文字符串哈希例5）
E. HDU4821 String（本文字符串哈希例6）
F. [CF727E Games on a CD(本文字符串哈希例7外链)](https://www.luogu.com.cn/blog/xjzsq/solution-cf727e)
------------
3/9update:第二次训练的部分题目：
D. [POJ3690 Constellations（本文字符串哈希例2，长度过长故单独成篇）](https://www.luogu.com.cn/blog/xjzsq/poj3690-constellations)
E. CF149E Martian Strings（本文KMP算法例题）
F. CF1137B Camp Schedule（本文KMP算法例题）
H. CF898F Restoring the Expression（本文字符串哈希例3）
## STL中的string
传送门:[STL string 字符串](https://www.luogu.com.cn/blog/xjzsq/stlstring-zi-fu-chuan)
## KMP算法
### 算法思想
以$O(M+N)$从目标串($len=M$)中找到模式串($len=N$)的算法。
核心是next数组，该数组记录了模式串的前$i$位中前缀和后缀完全匹配的最长位数。这样，如果在某一位匹配失败，不减小目标串的下标，而是减小模式串匹配到的位置的下标，而这个移动到的位数已经被预处理到了$next[i]$中。
譬如字符串`ABCABD`的`next`数组中的值为:
|$i$|1|2|3|4|5|6|
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
|$next[i]$|0|0|0|1|2|0|
在目标串中匹配时，如果当前字符与待匹配字符第$j+1$位不同，那么根据$next[j]$向前回溯到上一次匹配到相同前缀的模式串第$j$位，如果$j==0$则直接进行匹配。
### next数组的妙用
1. 求字符串循环节$O(n)$
求一个长度为n的字符串s的最小循环节，最小循环节指满足s可以由若干个t接在一起得到的长度最小的t。
结论:如果$(n-next[n])$是$n$的因子，那么循环节就是$(n-next[n])$，否则是$n$
### 核心代码/模板题
[【模板】KMP字符串匹配](https://www.luogu.com.cn/problem/P3375)
```cpp
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1000005;
char s1[maxn],s2[maxn];
int n,m,next[maxn],j;
int main()
{
scanf("%s%s",s1+1,s2+1);
n=strlen(s2+1);
m=strlen(s1+1);
for(register int i=2;i<=n;i++)
{
while(j>0&&s2[i]!=s2[j+1])j=next[j];
if(s2[i]==s2[j+1])j++;
next[i]=j;
}
j=0;
for(register int i=1;i<=m;i++)
{
while(j>0&&s1[i]!=s2[j+1])j=next[j];
if(s1[i]==s2[j+1])j++;
if(j==n)printf("%d\n",i-n+1),j=next[j];
}
for(register int i=1;i<=n;i++)printf("%d ",next[i]);
return 0;
}
```
### CF1137B Camp Schedule
#### 题目链接
https://codeforces.com/problemset/problem/1137/B
#### 题目大意
重排列一个01串$s$，使得在重排后的01串$s'$中能匹配到最多的01串$t$。
#### 思路
这个题也是对`KMP`算法中$next$数组的灵活运用，配合贪心的思想解决。
首先，尽可能构造$t$，构造出完整的$t$以后，令记录构造到$t$的位数的下标变量$j=next[j]$，也就是让重排后的串中，后一个$t$的前缀和前一个$t$的后缀重合位数最大，直到$1$或者$0$不足，直接输出剩下的另一个数字即可。
#### code
``` cpp
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 500005;
char s[maxn],t[maxn];
int n,m,next[maxn],j,ans,num1,num0;
int main()
{
scanf("%s%s",s+1,t+1);
n=strlen(t+1);
m=strlen(s+1);
j=0,ans=0;
for(register int i=1;i<=m;i++)
if(s[i]=='1')num1++;
else num0++;
for(register int i=2;i<=n;i++)
{
while(j>0&&t[i]!=t[j+1])j=next[j];
if(t[i]==t[j+1])j++;
next[i]=j;
}
if(m<n)
{
while(num0--)putchar('0');
while(num1--)putchar('1');
return 0;
}
else
{
j=0;
for(register int i=1;i<=m;i++)
{
if(t[j+1]=='1')
{
if(num1>0)putchar(t[j+1]),num1--,j++;
else
{
while(num0--)putchar('0');
return 0;
}
}
else
{
if(num0>0)putchar(t[j+1]),num0--,j++;
else
{
while(num1--)putchar('1');
return 0;
}
}
if(j==n)j=next[j];
}
}
return 0;
}
```
### CF149E Martian Strings
#### 题目链接
https://codeforces.com/problemset/problem/149/E
https://www.luogu.com.cn/problem/CF149E
#### 题目大意
已知一长度为$n$的字符串$s$和$q$个字符串，求这$q$个字符串中，有多少个可以由在$s$中找到两不相交子集连接得到。
#### 思路（KMP法，AC自动机似乎也可做，安排上了）
洛谷黑题(难度评级NOI/NOI+/CTSC)真的把我吓到了，反而意外的好写，恶意评分实锤...（也许AC自动机真就这么难写？）
按照题目需要判断是否能找出两个不相交子集，使他们连接起来可以构成某些字符串。既然是字符串匹配，那就肯定是`KMP`了，但是这个是裂成两部分的`KMP`，那就做两遍`KMP`呗。于是正着和反着分别求一遍`KMP`，求`KMP`过程中把$q$中每个字符第一次匹配到$s$的位置记录下来，最后$O(n)$枚举两个不相交子串的长度，判断是不是能够不相交（也就是判断裂开的那两个字符第一次匹配到的位置是不是一个在左，一个在右，中间差1以上）即可。
#### code
``` cpp
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e5+7,maxm = 1005;
int m,len,lenp,next[maxm],ansmin[maxm],ansmax[maxm],ans;
char s[maxn],p[maxm],sr[maxn],pr[maxm];
int main()
{
scanf("%s%d",s+1,&m);
len = strlen(s+1);
for(register int i=1;i<=len;i++)sr[i]=s[len-i+1];
while(m--)
{
memset(ansmin,0,sizeof(ansmin));
memset(ansmax,0,sizeof(ansmax));
scanf("%s",p+1);
lenp = strlen(p+1);
for(register int i=1;i<=lenp;i++)pr[i]=p[lenp-i+1];
int j=0;
for(register int i=2;i<=lenp;i++)
{
while(j&&p[i]!=p[j+1])j=next[j];
if(p[i]==p[j+1])j++;
next[i]=j;
}
j=0;
for(register int i=1;i<=len;i++)
{
while(j&&s[i]!=p[j+1])j=next[j];
if(s[i]==p[j+1])j++;
if(!ansmin[j])ansmin[j]=i;
if(j==lenp)break;
}
j=0;
for(register int i=2;i<=lenp;i++)
{
while(j&&pr[i]!=pr[j+1])j=next[j];
if(pr[i]==pr[j+1])j++;
next[i]=j;
}
j=0;
for(register int i=1;i<=len;i++)
{
while(j&&sr[i]!=pr[j+1])j=next[j];
if(sr[i]==pr[j+1])j++;
if(!ansmax[j])ansmax[j]=i;
if(j==lenp)break;
}
for(register int i=1;i<lenp;i++)
{
if((!ansmin[i])||(!ansmax[lenp-i]))continue;
if(ansmin[i]<len-ansmax[lenp-i]+1)
{
ans++;
break;
}
}
}
printf("%d",ans);
return 0;
}
```
### CF535D Tavas and Malekas
#### 题目链接
https://codeforces.com/problemset/problem/535/D
https://www.luogu.com.cn/problem/CF535D
#### 题目大意
把字符串$p$从第$a_1,a_2,\cdots,a_m$位开始插入到长度为$n$的字符串中，没有被插入的位置可以是任意字母(26个)，求合法字符串的个数对$1e9+7$取模后的值。如果在插入过程中冲突，则合法字符串个数为0。
#### 思路（KMP法,字符串哈希法见下面）
只要读懂了题（英语太差，开始根本读不懂题），就会发现答案就是没有插入字母位数的26次方（快速幂取模），虽然空位可以线性求出，但最大的问题是如何判断插入过程中是否冲突。
插入过程中是否冲突即是看模式串的相同长度的前缀和后缀是否完全匹配。考虑到`KMP`算法中$next[i]$表示的是前$i$位后缀和前缀相同的最长长度，那么$next[len]$($len$代表模式串总长度)就表示整体字符串前缀和后缀能匹配的最长长度，此时模式串的前$next[len]$位和后$next[len]$位完全相同，那么只需要在前$i$位继续寻找更小的完全匹配的前缀和后缀的位数即可（也就是把在前面找前缀，在后面找后缀的工作全部转移到了已经求出的前缀这里），令$i=next[i]$，那么$next[i]$就表示前$i$位中前缀和后缀匹配的最大位数，然后重复让$i=next[i]$，不断缩小范围直到$i=0$，至此就预处理出了所有合法的前缀和后缀相同的位数，到后面直接判断位数是否合法即可。
对于$next[i]$，这里放上[卞老板博客](https://ketchuppp.xyz/post/Codeforces535D-Tavas-and-Malekas/)里面的图来帮助理解:
#### code
``` cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
const int maxn = 1e6+7,mod = 1e9+7;
long long n,m,len,y[maxn],next[maxn],ok[maxn],on;
char p[maxn];
long long power(long long x,long long p)
{
long long ans=1;
while(p)
{
if(p&1)ans=(ans*x)%mod;
p>>=1,x=(x*x)%mod;
}
return ans;
}
int main()
{
scanf("%lld%lld%s",&n,&m,p+1);
len = strlen(p+1);
int j=0;
for(register int i=2;i<=len;i++)
{
while(j&&p[i]!=p[j+1])j=next[j];
if(p[i]==p[j+1])j++;
next[i]=j;
}
for(register int i=len;i;i=next[i])ok[next[i]]=1;
for(register int i=1;i<=m;i++)
{
scanf("%lld",&y[i]);
if(i>1)
{
if(y[i]-y[i-1]<len&&(!ok[y[i-1]+len-y[i]]))
{
putchar('0');
return 0;
}
else on+=std::min(y[i]-y[i-1],len);
}
if(i==m)on+=len;
}
printf("%lld",power(26,n-on));
return 0;
}
```
### P2375 [NOI2014]动物园
#### 题目链接
https://www.luogu.com.cn/problem/P2375
#### 题意
已知一个字符串$s$，求所有$(num[i]+1)$的乘积对$1e9+7$取模的结果，$num[i]$为$s[1..i]$中不相交且完全相同的前缀和后缀的数量。
#### 思路
仍然考虑`KMP`算法中$next[i]$的含义，在上面的`CF535D`中我们知道了$next[i]$表示前$i$位的字符串前缀和后缀匹配的最大位数，而令$i'=next[i]$后，$next[i']$表示当前$s[1..i']$中前缀和后缀匹配的最大位数的同时，这个后缀也会和$s[1..i]$的相同长度的后缀完全匹配，因此我们可以通过不断使$i=next[i]$来不断获得更短的完全匹配的前缀和后缀，直到$next[i]=0$。这个过程中，因为要满足前缀和后缀不重合，因此必须满足$next[i]\times 2 \leq n$，这样我们就得到了下面的代码：
```cpp
for(register int i=j=2;i<=len;i++,j=i)
{
int tmp=1;
while(next[j])
{
if((next[j]<<1)<=i)tmp++;
j=next[j];
}
ans=ans*tmp%mod;
}
```
但是，这样做太暴力了，T掉了一半的点...
因此我们考虑怎么优化——我们注意到对于每个$i$，$next[i]$只有一个，而$k=next[i]$却可以对应很多个$i$，是不是特别像一个树形的结构？
于是我们建一棵以$0$为根节点的树，并且使用$O(logn)$复杂度的倍增来代替$O(n)$的$i=next[i]$，这里要使用倍增跳两次，第一次从$i$跳到$next[i']\times 2 \leq i$，之后设个临时变量加每次跳的层数，直到跳到$0$。
时间复杂度$O(t\times nlogn)$,洛谷不开O2只有80分，开了O2就可以AC了。
什么？其实不用倍增？其实跳到满足$next[i']\times 2 \leq i$所需要的时间并不高，只需要预处理$i=next[i]$跳到$0$的深度就能做到$O(n)$？好像是这么回事，不过，可以做到$O(n)$的关键在于，需要和求$next[i]$得时候一样保留$j$的值，这样就可以保证跳到满足$next[i']\times 2 \leq i$所需要的时间最短了，另外需要注意的是，记录深度的数组要令$dep[1]=1$，原因是我们遍历从$i=2$开始，导致忽视了$1$的深度。总体时间复杂度$O(t\times n)$，从下面两个OJ的实际运行速度来看优化还是非常大的。
#### code
复杂度$O(t\times nlogn)$，洛谷O2 2.03s，UOJ2252ms
```cpp
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e6+7,mod = 1e9+7;
int t,len,next[maxn],f[21][maxn];
long long ans=1;
char s[maxn];
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%s",s+1);
len = strlen(s+1);
int j=0;
for(int i=2;i<=len;i++)
{
while(j&&s[j+1]!=s[i])j=f[0][j];
if(s[j+1]==s[i])j++;
f[0][i]=j;
}
for(register int i=1;i<=19;++i)
for(register int j=1;j<=len;++j)
f[i][j]=f[i-1][f[i-1][j]];
for(register int i=2;i<=len;i++)
{
int k=i,tmp=1;
for(int j=19;j>=0;j--)
if((f[j][k]<<1)>i)k=f[j][k];
for(int j=19;j>=0;j--)
if(f[j][k])tmp+=(1<<j),k=f[j][k];
ans=ans*tmp%mod;
}
for(register int i=2;i<=len;i++)
{
j=i;int tmp=0;
while(next[j])
{
if((next[j]<<1)<=i)tmp++;
j=next[j];
}
}
printf("%lld\n",ans);
ans=1;
}
return 0;
}
```
复杂度$O(t\times n)$，洛谷O2 209ms，UOJ总用时135ms
``` cpp
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e6+7,mod = 1e9+7;
int n,len,next[maxn],dep[maxn];
long long ans=1;
char s[maxn];
int main()
{
scanf("%d",&n);
while(n--)
{
scanf("%s",s+1);
len = strlen(s+1);
int j=0;dep[1]=1;
for(int i=2;i<=len;i++)
{
while(j&&s[j+1]!=s[i])j=next[j];
if(s[j+1]==s[i])j++;
next[i]=j;dep[i]=dep[j]+1;
}
j=0;
for(register int i=2;i<=len;i++)
{
while(j&&s[j+1]!=s[i])j=next[j];
if(s[j+1]==s[i])j++;
while((j<<1)>i)j=next[j];
ans=ans*(dep[j]+1)%mod;
}
printf("%lld\n",ans);
ans=1;
}
return 0;
}
```
## 字符串哈希
### 算法思想
通过把字符串看成多项式求值来将字符串的前$i$位压缩成$i$个整数，从而快速计算出一个子串的hash值，再通过比较两个子串的hash值是否相同来判断两子串是否相同。
### 核心代码
$h[i]$表示字符串前$i$位的hash值,$p[i]$表示$base^i$，第三行$hash\_s[i][j]$是$s$的子串$s[i..j]$的hash值
``` cpp
for(register int i=1;i<=n;i++)h[i]=(h[i-1]*base+s[i])%mod;
p[0]=1;for(register int i=1;i<=n;i++)p[i]=p[i-1]*base%mod;
hash_s[i][j]=(h[j]-h[i-1]*p[j-i+1]%mod+mod)%mod;
```
### 无符号整数溢出hash
在数据中不专门卡的情况下，可以不用模数$mod$，而是直接把数字存到`unsigned long long`中，按照`unsigned long long`的性质，里面的数字溢出后相当于对$2^{64}$取模。（但是毒瘤出题人或者cf上会有数据卡`ull`，慎用！）
### 双hash
mod有两个的hash，其他一模一样
### 二维字符串哈希
顾名思义，就是对字符矩阵求hash值。
计算方法是先求每行的哈希值，然后把各行的哈希值使用另外一个基数求出整体的哈希值。而求子矩阵的哈希值时，使用了二维差分的思想。
#### 核心代码
预处理大小为$n\times m$的字符矩阵$s$中子矩阵的哈希值。
``` cpp
for(register int i=1;i<=n;i++)
for(register int j=1;j<=m;j++)
h1[i][j]=(h1[i][j-1]*base1+s[i][j])%mod;
for(register int j=1;j<=m;j++)
for(register int i=1;i<=n;i++)
h2[i][j]=(h2[i-1][j]*base2+h1[i][j])%mod;
for(register int i=1;i<=n;i++)p1[i]=p1[i-1]*base1;
for(register int i=1;i<=m;i++)p2[i]=p2[i-1]*base2;
```
求子矩阵的哈希值(子矩阵的左上角坐标为$(x,y)$，大小为$a\times b$)：
``` cpp
inline long long get_hash(int x,int y,int a,int b)
{
return ((h2[x+a-1][y+b-1]-h2[x+a-1][y-1]*p1[b]%mod-h2[x-1][y+b-1]*p2[a]%mod+h2[x-1][y-1]*p2[a]*p1[b]%mod)%mod+mod)%mod;
}
```
#### 【板子】UVA11019 Matrix Matcher
输入两个字符矩阵，判断第二个矩阵在第一个矩阵中出现了多少次。就是二维字符串哈希的模板题。
```cpp
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1005,base1=131,base2=13331;
char matrix[maxn][maxn];
unsigned long long h[maxn][maxn],n,m,p,q,p1[maxn],p2[maxn],hh[maxn],hh2,ans,t;
inline unsigned long long get_hash(int x,int y,int a,int b)
{
return h[x+a-1][y+b-1]-h[x+a-1][y-1]*p1[b]-h[x-1][y+b-1]*p2[a]+h[x-1][y-1]*p2[a]*p1[b];
}
int main()
{
scanf("%llu",&t);
while(t--)
{
scanf("%llu%llu",&n,&m);
for(register int i=1;i<=n;i++)
scanf("%s",matrix[i]+1);
for(register int i=1;i<=n;i++)
for(register int j=1;j<=m;j++)
h[i][j]=h[i][j-1]*base1+matrix[i][j];
for(register int j=1;j<=m;j++)
for(register int i=1;i<=n;i++)
h[i][j]=h[i-1][j]*base2+h[i][j];
p1[0]=1,p2[0]=1;
for(register int i=1;i<=n;i++)p1[i]=p1[i-1]*base1;
for(register int i=1;i<=m;i++)p2[i]=p2[i-1]*base2;
scanf("%llu%llu",&p,&q);
for(register int i=1;i<=p;i++)
scanf("%s",matrix[i]+1);
memset(hh,0,sizeof(hh));
for(register int i=1;i<=p;i++)
for(register int j=1;j<=q;j++)
hh[i]=(hh[i]*base1+matrix[i][j]);
ans=hh2=0;for(register int i=1;i<=p;i++)hh2=(hh2*base2+hh[i]);
for(register int i=1;i+p-1<=n;i++)
for(register int j=1;j+q-1<=m;j++)
if(get_hash(i,j,p,q)==hh2)ans++;
printf("%llu\n",ans);
}
return 0;
}
```
### 例1.CF535D Tavas and Malekas
#### 其他信息见上方
#### 思路（字符串哈希法）
前面分析略。
对于计算相同长度的前缀和后缀是否完全匹配，除了利用`KMP`算法求出的$next$数组外，还可以通过字符串哈希看哈希值是否相同实现。
#### code
debug:开始没有弄清楚长度为$y[i-1]\times len-y[i]$计算$hash$的$l,r$参数。
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
const int maxn = 1e6+7,mod = 1e9+7;
long long n,m,len,y[maxn],on,base = 233,mmod = 19260817,pp[maxn],h[maxn];
char p[maxn];
long long power(long long x,long long p)
{
long long ans=1;
while(p)
{
if(p&1)ans=(ans*x)%mod;
p>>=1,x=(x*x)%mod;
}
return ans;
}
inline long long hash(long long l,long long r)
{
return (h[r]-(h[l-1]*pp[r-l+1]%mmod)+mmod)%mmod;
}
int main()
{
scanf("%lld%lld%s",&n,&m,p+1);
len = strlen(p+1);pp[0]=1;
for(register int i=1;i<=len;i++)h[i]=(h[i-1]*base+p[i])%mmod,pp[i]=pp[i-1]*base%mmod;
for(register int i=1;i<=m;i++)
{
scanf("%lld",&y[i]);
if(i>1)
{
if(y[i]-y[i-1]<len&&hash(y[i]-y[i-1]+1,len)!=h[y[i-1]+len-y[i]])
{
putchar('0');
return 0;
}
on+=std::min(len,y[i]-y[i-1]);
}
if(i==m)on+=len;
}
printf("%lld",power(26,n-on));
return 0;
}
```
### 例2. POJ3690 Constellations
#### 题解链接
https://www.luogu.com.cn/blog/xjzsq/poj3690-constellations
### 例3. CF898F Restoring the Expression
#### 题目链接
https://codeforces.com/problemset/problem/898/F
https://www.luogu.com.cn/problem/CF898F
#### 题意
往一串数字中塞一个加号和一个等号（加号在等号左边），使得等式成立，求成立的等式。
#### 思路
先确定等号的位置（因为位数限制，等号的位置只可能介于$\lfloor{len\over 2}\rfloor$和$\lceil{\frac{2}{3}len}\rceil$之间） ，然后此时加号的位置只可能有4个，假设结果的位数为$sum$，那么两个加数中较长的加数的长度只可能是$sum$和$sum-1$（原因是按照加法的运算规律，计算过程中只可能进一位或者不进位），而较长的加数可以在加号左边，也可能在加号右边，因此就有了$2\times 2 = 4$中情况。
#### code
``` cpp
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e6+7,base=10,mod=19491001;
char s[maxn];
long long len,n,h[maxn],p[maxn],sum,tot;
inline long long gethash(int l,int r)
{
return ((h[r]-h[l-1]*p[r-l+1])%mod+mod)%mod;
}
inline bool check(long long x,long long y)//check s[1,x]+s[x+1,y]?=s[y+1,len]
{
if(x<=0||y<=0||y<x)return false;
if(x>1&&s[1]=='0')return false;
if(y!=x+1&&s[x+1]=='0')return false;
if((gethash(1,x)+gethash(x+1,y))%mod==sum)
{
for(register int i=1;i<=x;i++)putchar(s[i]);putchar('+');
for(register int i=x+1;i<=y;i++)putchar(s[i]);putchar('=');
for(register int i=y+1;i<=len;i++)putchar(s[i]);
return true;
}
return false;
}
int main()
{
scanf("%s",s+1);
len = strlen(s+1),p[0]=1;
for(register int i=1;i<=len;i++)h[i]=(h[i-1]*base+s[i]-'0')%mod,p[i]=p[i-1]*base%mod;
n=len-len/3;
for(int i=len>>1;i<=n;i++)
{
sum=gethash(i+1,len),tot=len-i;
if(check(tot,len-tot))return 0;
if(check(len-(tot<<1),len-tot))return 0;
if(check(tot-1,len-tot))return 0;
if(check(len-(tot<<1)+1,len-tot))return 0;
}
return 0;
}
```
### 例4.【模板】后缀排序（字符串哈希法）
#### 题目链接
[洛谷P3809](https://www.luogu.com.cn/problem/P3809)
[UOJ#35.后缀排序](http://uoj.ac/problem/35)
#### 题意
对一个字符串的后缀排序，输出顺序。
#### 思路（字符串哈希法）
可以通过二分+字符串hash以$logn$求出两字符串LCP（最长公共前缀），然后就可以通过比较LCP之后的字符直接得知两字符串的大小了，以此结果套个sort排序，总时间复杂度$O(nlog^2n)$。
洛谷上因为数据达到了$1e6$，只能得$70$分，UOJ上为$1e5$，可以AC。
#### code
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1e6+7,base = 233,mod = 19491001;
char s[maxn];
long long len,h[maxn],ans[maxn],p[maxn];
inline long long get_hash(int x,int y)
{
return (h[y]-h[x-1]*p[y-x+1]%mod+mod)%mod;
}
inline int lcp(int x,int y)
{
int l=0,r=min(len-x,len-y)+1;
while(l<r)
{
int mid=l+r+1>>1;
if(get_hash(x,x+mid-1)==get_hash(y,y+mid-1))l=mid;
else r=mid-1;
}
return l;
}
inline bool cmp(int x,int y)
{
int l = lcp(x,y);
return s[x+l]<s[y+l];
}
int main()
{
scanf("%s",s+1);
len = strlen(s+1);p[0]=1;
for(register int i=1;i<=len+1;i++)h[i]=(h[i-1]*base+s[i])%mod,ans[i]=i,p[i]=p[i-1]*base%mod;
sort(ans+1,ans+len+1,cmp);
for(register int i=1;i<=len;i++)printf("%lld ",ans[i]);
putchar('\n');for(register int i=1;i<len;i++)printf("%lld ",lcp(ans[i],ans[i+1]));//洛谷上注释此行输出
return 0;
}
```
### 例5. CF985F Isomorphic Strings
#### 题目链接
https://www.luogu.com.cn/problem/CF985F
https://codeforces.com/contest/985/problem/F
#### 题意
已知一字符串$s$,判断两子串中的字符是否能一一映射相等。
#### 思路
思路比较特殊，直接用比较哈希并不能解决问题，只需要把26个字母分开计算哈希值，计算出来排序比较是否一一相等即可。本题华点是把26个字母分开处理，妙哉、妙哉~
#### code
``` cpp
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=2e5+7,base=233,mod=19491001;
int n,m,xx[30],yy[30];
long long h[30][maxn],p[maxn];
char s[maxn];
inline long long get_hash(int c,int l,int r)
{
return (h[c][r]-h[c][l-1]*p[r-l+1]%mod+mod)%mod;
}
inline bool check(int x,int y,int len)
{
for(register int i=0;i<26;i++)xx[i]=get_hash(i,x,x+len-1),yy[i]=get_hash(i,y,y+len-1);
sort(xx,xx+26);sort(yy,yy+26);
for(register int i=0;i<26;i++)if(xx[i]!=yy[i])return false;
return true;
}
int main()
{
scanf("%d%d%s",&n,&m,s+1);
for(register int k=0;k<26;k++)
for(register int i=1;i<=n;i++)
h[k][i]=(h[k][i-1]*base+(s[i]==k+'a'))%mod;
p[0]=1;for(register int i=1;i<=n;i++)p[i]=p[i-1]*base%mod;
while(m--)
{
int x,y,len;
scanf("%d%d%d",&x,&y,&len);
if(check(x,y,len))printf("YES\n");
else printf("NO\n");
}
return 0;
}
```
#### 例6. HDU4821 String
#### 题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=4821
#### 题意
求字符串$s$中满足条件的长度为$m\times l$的子串的个数，该子串满足划分为$m$个长度为$l$的串后各不相同。
#### 思路
开始写了个暴力一点的做法光荣TLE...
正解应该是枚举第一个区间开始的位置，使用map统计长度为$l$的$m$个子串的哈希值，如果map的大小为$m$则答案+1，之后删掉最靠前的一个子串的哈希值，后面再加一个子串的哈希值，再次判断答案，直至到最后。
#### code
``` cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int maxn = 1e5+7,base = 233,mod = 19491001;
int m,l,len,ans,n;
char s[maxn];
long long h[maxn],p[maxn];
map<long long,int> M;
inline long long get_hash(int x)
{
return (h[x+l-1]-h[x-1]*p[l]%mod+mod)%mod;
}
int main()
{
p[0]=1;for(register int i=1;i<=maxn;i++)p[i]=p[i-1]*base%mod;
while(scanf("%d%d",&m,&l)!=EOF)
{
scanf("%s",s+1);
len=strlen(s+1),ans=0,n=len-l+1;
for(register int i=1;i<=len;i++)h[i]=(h[i-1]*base+s[i])%mod;
for(register int i=1;i<=l&&i+m*l<=len;i++)
{
M.clear();
for(register int j=0;j<m;j++)M[get_hash(i+j*l)]++;
if(M.size()==m)ans++;
for(register int j=i+m*l;j<=n;j+=l)
{
long long t=get_hash(j),tr=get_hash(j-m*l);M[tr]--;
if(!M[tr])M.erase(tr);
M[t]++;
if(M.size()==m)ans++;
}
}
printf("%d\n",ans);
}
return 0;
}
```
### 例7 BZOJ3916 friends
#### 题目链接
http://www.lydsy.com/JudgeOnline/problem.php?id=3916
#### 题意
在字符串$s$中删去一个字符，得到的字符串为$t$重复两次。若$t$不存在，则输出"NOT POSSIBLE",若有多个符合条件的$t$，输出"NOT UNIQUE"，否则输出$t$。
#### 思路
首先排除偶数长度的输入（NOT POSSIBLE）。
然后通过统计字符出现次数找出需要被删去的字符（出现奇数次），并排除多个的情况（NOT POSSIBLE）。
之后枚举所有和被删去的字符相同的位置，判断前后两半是否相等，若相等则存入map。
最后判断map的大小，若为0则为"NOT POSSIBLE"，若为1则输出答案，若大于1则为"NOT UNIQUE"
#### code
``` cpp
#include<cstdio>
#include<map>
using namespace std;
const int maxn = 2000005,base=233,mod=194910071;
int n,num[27],first;
long long h[maxn],p[maxn],x,y;
char s[maxn],now;
map<long long ,int> M;
inline long long gethash(int l,int r)
{
if(r<l)return 0;
return (h[r]-h[l-1]*p[r-l+1]%mod+mod)%mod;
}
int main()
{
scanf("%d%s",&n,s+1);p[0]=1;
if(!(n&1)){printf("NOT POSSIBLE");return 0;}
for(register int i=1;i<=n;i++)h[i]=(h[i-1]*base+s[i])%mod,p[i]=p[i-1]*base%mod,num[s[i]-'A']++;
for(register int i=0;i<26;i++)if(num[i]&1)
if(now==0)now=i+'A';
else{printf("NOT POSSIBLE");return 0;}
for(register int i=1;i<=n;i++)
if(s[i]==now)
{
if(i>(n>>1))x=gethash(1,n>>1),y=(gethash((n>>1)+1,i-1)*p[n-i]+gethash(i+1,n))%mod;
else x=(gethash(1,i-1)*p[(n>>1)-i+1]+gethash(i+1,(n>>1)+1))%mod,y=gethash(2+(n>>1),n);
if(x==y){M[x]++;if(!first)first=i;}
}
if(!first){printf("NOT POSSIBLE");return 0;}
if(M.size()>1)printf("NOT UNIQUE");
else
{
if(first>(n>>1))
{
n>>=1;
for(register int i=1;i<=n;i++)putchar(s[i]);
}
else
{
n>>=1;
for(register int i=1;i<=first-1;i++)putchar(s[i]);
for(register int i=first+1;i<=n+1;i++)putchar(s[i]);
}
}
return 0;
}
```
### 例8. CF727E Games on a CD
#### 题解链接：https://www.luogu.com.cn/blog/xjzsq/solution-cf727e
## 字符串DP
有些题目把字符串和DP融合到一起考察，目前还没有找到规律性的结论。
### CF1183H Subsequences (hard version)
#### 题目链接
https://www.luogu.com.cn/problem/CF1183H
https://codeforces.com/problemset/problem/1183/H
#### 题意
求在长度为$n$的字符串$s$中删掉$0\sim n$个字符得到$k$个本质不同的子序列所需要删去字母个数的总和。
#### 思路
设$dp[i][j]$表示前$i$个字符中长度为$j$的本质不同的子序列个数，$pre[i]$表示第$i+1$字母上次出现的位置，则:
$$dp[i][j]=\begin{cases}dp[i-1][j]+dp[i-1][j-1]&pre[s[i]]=0\\ dp[i-1][j]+dp[i-1][j-1]-dp[pre[i]-1][j-1]&pre[s[i]]\neq 0\end{cases}$$
上面的公式中，$dp[i-1][j]$表示删掉$s[i]$，$dp[i-1][j-1]$表示不删掉$s[i]$，当前面出现过$s[i]$时，就会出现重复，因此需要减掉前面重复计算的部分，即$dp[pre[i]-1][j-1]$，原因是前$pre[i]-1$个字符中长度为$j-1$的子序列后面加上$s[pre[i]]$和$s[i]$是一样的，所以造成了重复。
#### code
``` cpp
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=105;
long long n,k,ans,dp[maxn][maxn],pre[27],now;
char s[maxn];
int main()
{
scanf("%lld%lld%s",&n,&k,s+1);
dp[0][0]=1;
for(register int i=1;i<=n;i++)
{
dp[i][0]=1;
for(register int j=1;j<=i;j++)
if(pre[s[i]-'a']==0)dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
else dp[i][j]=dp[i-1][j]+dp[i-1][j-1]-dp[pre[s[i]-'a']-1][j-1];
pre[s[i]-'a']=i;
}
now=n;
while(k>=dp[n][now]&&now>-1)k-=dp[n][now],ans+=(n-now)*dp[n][now],now--;
ans+=(n-now)*k;
if(now<0&&k>0)printf("-1");
else printf("%lld",ans);
return 0;
}
```
### 【最小编辑距离】UVA1207 AGTC
#### 题解：https://www.luogu.com.cn/blog/xjzsq/solution-uva1207
## trie字典树
### 算法思想
构建一个树，使得每条从根节点到叶节点（或者中间的某个节点）的路径连起来组成一个字符串，从而存储字符串，节省存储空间。
令$trie[i][j]$表示编号为$i$的节点的字符为$j$时，连接的子节点编号。则我们可以通过不断更新$now=trie[now][s[i]]$来匹配字符串$s$，代码详见例2。(比较乱是因为实在描述不清楚了...)
### 01trie
将二进制看成字符串后构成的字典树，常用于带有xor操作的题目，详见例1。
### 例1 CF1285D Dr. Evil Underscores
#### 题目链接
https://www.luogu.com.cn/problem/CF1285D
https://codeforces.com/problemset/problem/1285/D
#### 题意
已知$n$个数$a[1..n]$，求$x$满足$max\{a[i]\oplus x\}$最小，输出这个最小值。
#### 思路
首先建个01trie树，然后从最高位开始向下深搜，如果当前位0/1都有子树，则该位答案必为1，然后分别向0和向1继续搜索，如果只有一边有子树，则该位答案可以为0，然后向下搜索即可。
#### code
``` cpp
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1e5+7;
long long n,a[maxn],trie[maxn<<5][2],cnt,ans=2147483647;
inline void insert(long long x)
{
int pos=30,u=0;
while(pos--)
if(!trie[u][(x>>pos)&1])u=trie[u][x>>pos&1]=++cnt;
else u=trie[u][(x>>pos)&1];
return;
}
inline void dfs(long long x,long long now)
{
if(trie[x][0]&&trie[x][1])dfs(trie[x][0],now<<1|1),dfs(trie[x][1],now<<1|1);
else if(trie[x][0])dfs(trie[x][0],now<<1);
else if(trie[x][1])dfs(trie[x][1],now<<1);
else ans=min(ans,now);
return;
}
int main()
{
scanf("%lld",&n);
for(register int i=1;i<=n;i++)scanf("%lld",&a[i]),insert(a[i]);
dfs(0,0);
printf("%lld",ans);
return 0;
}
```
### 例2 P2580 于是他错误的点名开始了
#### 题目链接
https://www.luogu.com.cn/problem/P2580
#### 题意
已知含有$n$个字符串的名单，进行$m$次点名，如果没有该名字输出`WRONG`,如果重复点名输出`REPEAT`,第一次正确点到输出`OK`。
#### 思路
trie树板子
#### code
``` cpp
#include<cstdio>
using namespace std;
const int maxn = 10005,maxm = 50;
int trie[maxn*maxm][26],n,m,top;
bool ok[maxn*maxm],has[maxn*maxm];
char s[maxm];
inline void insert(char* ss)
{
int now=0;
for(int i=0;ss[i]!='\0';i++)
if(!trie[now][ss[i]-'a'])now=trie[now][ss[i]-'a']=++top;
else now=trie[now][ss[i]-'a'];
ok[now]=1;
return;
}
inline void find(char* ss)
{
int now=0;
for(register int i=0;ss[i]!='\0';i++)
if(!trie[now][ss[i]-'a']){puts("WRONG");return;}
else now = trie[now][ss[i]-'a'];
if(!ok[now])puts("WRONG");
else if(has[now])puts("REPEAT");
else puts("OK"),has[now]=true;
return;
}
int main()
{
scanf("%d",&n);
while(n--)scanf("%s",&s),insert(s);
scanf("%d",&m);
while(m--)scanf("%s",&s),find(s);
return 0;
}
```
## AC自动机
### 算法思想
AC自动机即是在trie上做KMP。
首先，构造一个trie字典树。
然后，计算fail数组，满足：从根节点到节点$fail[i]$所代表的字符串是从根节点到节点$i$字符串的后缀。具体计算方式为，由根节点进行bfs，将待计算的点存入队列$Q$中，对于每个节点$i$，如果该节点$i$由字符$ch$指向的下一个节点$j=trie[i][ch]$存在，则更新节点$j$的$fail$值为节点$trie[fail[i]][ch]$的$fail$值（即如果在当前节点的下一节点失配，则会跳到当前节点的失配节点的下一节点继续进行匹配）；如果下一节点$trie[i][ch]$不存在，则向$trie[fail[i]][ch]$连一条边（也就是到其对应的失配节点继续匹配）。
构造完成后，字典树$trie$经过了连边就会变成字典图。
查询的时候，同样由根节点$now=0$起始，对待匹配的字符串$s$从前往后匹配，首先判断当前结点$now$通过字符$s[i]$连接的下个点$trie[now][s[i]]$是否存在，若不存在则为失配情况，将$now$调整为$fail[now]$，然后再更新到下个节点$now=trie[now][s[i]]$，之后按照题意对该节点的所有失配节点进行遍历计算结果（需要开一个变量遍历$fail$值）。
### 模板题
[P3808 【模板】AC自动机（简单版）](https://www.luogu.com.cn/problem/P3808)
``` cpp
#include<cstdio>
#include<queue>
using namespace std;
const int maxn = 1e6+7;
int n,trie[maxn][26],ok[maxn],top,fail[maxn];
char ss[maxn];
inline void insert(char* s)
{
int now=0;
for(register int i=0;s[i];i++)
if(!trie[now][s[i]-'a'])now=trie[now][s[i]-'a']=++top;
else now=trie[now][s[i]-'a'];
ok[now]++;
}
queue<int> Q;
inline void build()
{
for(register int i=0;i<26;i++)if(trie[0][i])Q.push(trie[0][i]);
while(!Q.empty())
{
int u=Q.front();Q.pop();
for(register int i=0;i<26;i++)
if(trie[u][i])fail[trie[u][i]]=trie[fail[u]][i],Q.push(trie[u][i]);
else trie[u][i]=trie[fail[u]][i];
}
}
inline void query(char *s)
{
int now=0,ans=0;
for(register int i=0;s[i];i++)
{
now=trie[now][s[i]-'a'];
for(register int j=now;j&&ok[j]!=-1;j=fail[j])
ans+=ok[j],ok[j]=-1;
}
printf("%d",ans);
}
int main()
{
scanf("%d",&n);
for(register int i=1;i<=n;i++)scanf("%s",&ss),insert(ss);
build();
scanf("%s",&ss);
query(ss);
return 0;
}
```
### POJ1204 Word Puzzles
#### 题目链接
http://poj.org/problem?id=1204
#### 题意
在一个$l\times c$的圈词游戏表里面找出$w$个给定的单词，输出单词开头字母的坐标($0-index$)和单词延伸的方向（从向上开始，按照顺时针把八个方向分别记为$A\sim H$）。
#### 思路
首先将需要找的单词构建成$trie$，并且构建AC自动机，然后从表的四个边上的点开始向可以延伸的方向进行匹配。（明明写了大概4~5h才A掉，思路却如此简单......但是理解透彻了AC自动机的原理，付出也算有回报吧！）
#### code
``` cpp
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 1005;
int l,w,c,top,trie[maxn*100][26],fail[maxn*100],ok[maxn*100],tx[]={1,1,0,-1,-1,-1,0,1},ty[]={0,-1,-1,-1,0,1,1,1};
char m[maxn][maxn],q[maxn];
struct node
{
int x,y;char c;
}ans[maxn];
inline void insert(char *s,int no)
{
int now=0,len=strlen(s);
for(register int i=len-1;i>-1;i--)
if(!trie[now][s[i]-'A'])now=trie[now][s[i]-'A']=++top;
else now=trie[now][s[i]-'A'];
ok[now]=no;
}
queue<int> Q;
inline void build()
{
for(register int i=0;i<26;i++)if(trie[0][i])Q.push(trie[0][i]);
while(!Q.empty())
{
int now=Q.front();Q.pop();
for(register int i=0;i<26;i++)
if(trie[now][i])fail[trie[now][i]]=trie[fail[now]][i],Q.push(trie[now][i]);
else trie[now][i]=trie[fail[now]][i];
}
}
inline void query(int x,int y,int on)
{
int now=0;
while(x>-1&&y>-1&&x<l&&y<c)
{
if(now&&(!trie[now][m[x][y]-'A']))now=fail[now];
now=trie[now][m[x][y]-'A'];
for(register int i=now;i;i=fail[i])
if(ok[i])ans[ok[i]].x=x,ans[ok[i]].y=y,ans[ok[i]].c=on+'A';
x+=tx[on],y+=ty[on];
}
}
int main()
{
scanf("%d%d%d",&l,&c,&w);
for(register int i=0;i<l;i++)scanf("%s",&m[i]);
for(register int i=1;i<=w;i++)scanf("%s",&q),insert(q,i);
build();
for(register int i=0;i<l;i++)
{
for(register int j=5;j<=7;j++)query(i,0,j);
for(register int j=1;j<=3;j++)query(i,c-1,j);
}
for(register int i=0;i<c;i++)
{
for(register int j=7;j<=9;j++)query(0,i,j%8);
for(register int j=3;j<=5;j++)query(l-1,i,j);
}
for(register int i=1;i<=w;i++)printf("%d %d %c\n",ans[i].x,ans[i].y,ans[i].c);
return 0;
}
```
### CF710F String Set Queries(AC自动机+二进制分组)
#### 题目链接
https://codeforces.com/contest/710/problem/F
https://www.luogu.com.cn/problem/CF710F
#### 题意
维护一个字符串集合，支持三种操作：
1. 加字符串
2. 删字符串
3. 查询集合中的所有字符串在给出的模板串中出现的次数
其中，操作次数$m\le3×10^5$，字符串总长度$\sum|s_i|\le3×10^5$
另外，本题强制在线，在每次输入后调用`fflush(stdout)`才能继续读入。
#### 思路
**调了一个通宵+一上午，终于AC了...成功通过洛谷第二个黑题！**（第一个似乎是个被恶意评分的水题）吐槽完了，下面是思路：
本题强制在线，因此并不能直接套用AC自动机板子，如果每次查询都重构一次AC自动机，复杂度达到$O(m\times |S|)$，复杂度已经到$1e10$级别，明显会超时。所以需要利用一种巧妙的方法——二进制分组来是复杂度降低到$O(m\times log|S|)$，轻松通过。
二进制分组，就是将$n$组数据按照其二进制位分组存储，比如，现在有$9$个字符串，写成二进制为$1001$，二进制位为$1$的数据为一组，也就是前$8$个字符串构建一棵trie树，最后一个字符串构建一棵trie树，当第$10$个字符串插入以后，先自己构建一棵trie树，然后发现其大小和前一个trie树相同，因此需要合并，之后不断合并相同的两棵trie树，合并完成后只需要对最后一个新合并的trie树重新跑一遍AC自动机即可满足要求，不难看出平均每次操作只对$log|S|$个字符串进行了求AC自动机操作，因此时间复杂度缩小到了$O(mlog|S|)$，而本题加字符串和删字符串是互不干扰，所以开两个trie的二进制分组，一个trie的二进制分组存加字符串，另一个存删字符串，查询的时候结果相减即是答案。
#### code
``` cpp
#include<cstdio>
#include<queue>
using namespace std;
const int maxn = 3e5+7;
int m,t,trie[maxn][26],ch[maxn][26],tp[2],root[2][maxn],top,num[maxn],sz[2][maxn],fail[maxn],tot[maxn];
inline int merge(int x,int y)
{
if(!x||!y)return x|y;
num[x]+=num[y];
for(register int i=0;i<26;i++)trie[x][i]=merge(trie[x][i],trie[y][i]);
return x;
}
inline void build(int x)
{
queue<int> Q;
for(register int i=0;i<26;i++)if(trie[x][i])fail[ch[x][i]=trie[x][i]]=x,Q.push(ch[x][i]);else ch[x][i]=x;
while(!Q.empty())
{
int now=Q.front();Q.pop();
for(register int i=0;i<26;i++)
if(ch[now][i]=trie[now][i])fail[ch[now][i]]=ch[fail[now]][i],Q.push(ch[now][i]);
else ch[now][i]=ch[fail[now]][i];
tot[now]=tot[fail[now]]+num[now];
//printf("tot:%d\n",tot[now]);
}
}
inline void insert(int o,char *s)
{
int u=root[o][++tp[o]]=++top;
for(register int i=0;s[i];i++)
if(trie[u][s[i]-'a'])u=trie[u][s[i]-'a'];
else u=trie[u][s[i]-'a']=++top;
num[u]++;sz[o][tp[o]]=1;
while(sz[o][tp[o]]==sz[o][tp[o]-1])
tp[o]--,sz[o][tp[o]]+=sz[o][tp[o]+1],merge(root[o][tp[o]],root[o][tp[o]+1]);
build(root[o][tp[o]]);
return;
}
inline int query(int o,char* s)
{
int ans=0;
for(register int i=1;i<=tp[o];i++)
{
int u=root[o][i];
for(register int j=0;s[j];j++)u=ch[u][s[j]-'a'],ans+=tot[u];
}
return ans;
}
char s[maxn];
int main()
{
scanf("%d",&m);
while(m--)
{
scanf("%d%s",&t,&s);
if(t==3)printf("%d\n",query(0,s)-query(1,s));
else insert(t-1,s);
fflush(stdout);
}
return 0;
}
```
## 后缀数组SA
### 算法思想
后缀数组算法（SA）的目的，是求出数组$sa$和$rk$，其中$sa[i]$为将后缀排序后排名为$i$的后缀的起始位置，$rk[i]$表示后缀数组排序后起始下标为$i$的后缀的排名。因此，这两个数组满足$sa[x]=y\Longleftrightarrow rk[y]=x$
一般来说采用倍增+基数排序的方法来$O(nlogn)$求解SA，下面的总结也是基于此方法的。而基于诱导排序的[SA-IS算法](https://www.luogu.com.cn/blog/ShadowassIIXVIIIIV/on-hou-zhui-shuo-zu-sa-is-suan-fa)复杂度珂以达到$O(n)$，但是由于太难了实在没有时间去学，所以暂时搁置待学。（DC3虽然$O(n)$但是又占空间又难写，直接pass）下面就是我对倍增+基数排序法求SA的理解总结。
按照倍增的思想，先求出所有长度为1的子串排名，然后再计算长度为2的子串排名，之后不断倍增子串的长度，直到倍增到整个字符串，这样只需要$log|S|$次排名即可完成任务。
通过把倍增后的字符串的前后两部分分别作为第一关键字和第二关键字排序，即可满足上述要求。但是快速排序的复杂度太高了，因为这里排序的数据范围不大，因此采用基数排序的方法$O(n)$进行排序。
直接采用基数排序的常数比较大，因此需要进行一些优化：
1. 排名过程中，第二关键字并不需要排序，假设要倍增的长度为w，那么只需要将第二关键字为空的w个位置提前，后面按照当前顺序直接存即可。
2. 将排序中用到的rk[oldsa[i]]提前用数组存起来，以加快速度
3. 每次更新基数排序的最大值，减小循环次数
以上就是SA算法的思想，但是在题目中广泛应用的，还有基于$sa$和$rk$计算出来的数组$height$。$height[i]$表示排名为$i$和$i-1$的后缀的LCP（最长公共前缀）。
在理解$O(n)$求解$height$数组前，需要以下引理：
$height[rk[i]]\ge height[rk[i-1]] - 1 $，证明方法见[oi-wiki](https://oi-wiki.org/string/sa/#on-height)，有了这个结论，我们就可以先求出$height[rk[i-1]]$，然后去计算下一个$height$的值了。
代码如下：（因为模板题里面没求，故先放这部分代码）
``` cpp
for(register int k=0,i=1;i<=len;i++)
{
if(k)--k;//也就是求出height[rk[i=1]]
while(s[i+k]==s[sa[rk[i]-1]+k])++k;//从height[rk[i-1]]的基础上如果之后依然相同则继续增长
h[rk[i]]=k;
}
```
### 模板题
[P3809【模板】后缀排序](https://www.luogu.com.cn/problem/P3809)(为了方便复制板子，加了求height的代码)
``` cpp
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e6+7;
char s[maxn];
int n,sa[maxn],id[maxn],px[maxn],rk[maxn],cnt[maxn],oldrk[maxn<<1],h[maxn];
inline bool cmp(int x,int y,int w)
{
return oldrk[x]==oldrk[y]&&oldrk[x+w]==oldrk[y+w];
}
int main()
{
scanf("%s",s+1);n = strlen(s+1);
int i,p,m=300;
//memset(cnt,0,sizeof(cnt));//多测去掉注释
for(i=1;i<=n;i++)++cnt[rk[i]=s[i]];
for(i=1;i<=m;i++)cnt[i]+=cnt[i-1];
for(i=n;i>0;i--)sa[cnt[rk[i]]--]=i;
for(register int w=1;w<n;w<<=1,m=p)
{
for(p=0,i=n;i>n-w;i--)id[++p]=i;
for(i=1;i<=n;i++)if(sa[i]>w)id[++p]=sa[i]-w;
memset(cnt,0,sizeof(cnt));
for(i=1;i<=n;i++)++cnt[px[i]=rk[id[i]]];
for(i=1;i<=m;i++)cnt[i]+=cnt[i-1];
for(i=n;i>0;i--)sa[cnt[px[i]]--]=id[i];
memcpy(oldrk,rk,sizeof(rk));
for(p=0,i=1;i<=n;i++)rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;
}
for(register int k=0,i=1;i<=n;i++)
{
if(k)--k;
while(s[i+k]==s[sa[rk[i]-1]+k])++k;
h[rk[i]]=k;
}
for(register int i=1;i<=n;i++)printf("%d ",sa[i]);
return 0;
}
```
### UVA11107 Life Forms
#### 题目链接
https://www.luogu.com.cn/problem/UVA11107
https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=23&page=show_problem&problem=2048
#### 题意
已知n个字符串，求所有长度最大的子串，满足在超过一半的字符串中出现。
#### 思路
吐槽：交了10发，学SA算法用了3天，写代码写了2天才A掉这个题...
看到长度最大即可想到二分，首先通过二分长度求出满足条件的子串的最大长度，然后依次判断输出满足条件的字符串即可。
而判断是否满足条件，则是巧妙地利用了height数组的性质，作为LCP，如果连续超过$n/2$个$height$都大于等于长度$l$，那么这些后缀共有长度至少为$l$的公共前缀，也就满足了题目条件。除此之外，因为height[i]是后缀排序后的结果，所以不会有其他不满足此条件但满足题目条件的字符串。
题目中的字符串有$n$个，只需要用不同的分割符隔开合并成一个字符串中即可，注意，字符型char的范围为$-128~127$，因此本题**不能**从$123(=97+26)$开始计算，而应从1开始，到97则跳到124，不要问我怎么知道的，因为这个问题被卡了一个中午...
另外，本题中比较特殊的是，需要计算子串在多少个字符串中出现，而不是出现次数，因此需要先预处理出每个字符属于哪个字符串（存到belong中）。
#### code
```cpp
#include<cstdio>
#include<cstring>
#include<set>
using namespace std;
const int maxn = 110005;
int n,belong[maxn],len,sa[maxn],rk[maxn],id[maxn],oldrk[maxn<<1],cnt[maxn],px[maxn],h[maxn];
char s[maxn];
inline bool cmp(int x,int y,int w)
{
return oldrk[x]==oldrk[y]&&oldrk[x+w]==oldrk[y+w];
}
inline bool check(int x)
{
set<int> S;S.insert(belong[sa[1]]);
for(register int i=2;i<=len;i++)
{
while(h[i]>=x&&i<=len)S.insert(belong[sa[i]]),i++;
if((S.size()<<1)>n)return true;
S.clear();
S.insert(belong[sa[i]]);
}
return false;
}
int main()
{
bool flag=false;
while(scanf("%d",&n),n)
{
if(flag)putchar('\n');else flag=true;
if(n==1)
{
scanf("%s",&s);
printf("%s\n",s);
continue;
}
char sp = 0;
for(register int i=1,prelen=1,nextlen;i<=n;i++,prelen=(len=nextlen)+1)
{
if(sp==96)sp=123;
scanf("%s",s+prelen);
nextlen=prelen+strlen(s+prelen);
for(register int j=prelen;j<nextlen;j++)belong[j]=i;
s[nextlen]=++sp;
}
int i,m=300;len--;
memset(cnt,0,sizeof(cnt));
for(i=1;i<=len;i++)++cnt[rk[i]=s[i]];
for(i=1;i<=m;i++)cnt[i]+=cnt[i-1];
for(i=len;i>0;i--)sa[cnt[rk[i]]--]=i;
for(register int w=1,p;w<=len;w<<=1,m=p)
{
for(p=0,i=len;i>len-w;i--)id[++p]=i;
for(i=1;i<=len;i++)if(sa[i]>w)id[++p]=sa[i]-w;
memset(cnt,0,sizeof(cnt));
for(i=1;i<=len;i++)++cnt[px[i]=rk[id[i]]];
for(i=1;i<=m;i++)cnt[i]+=cnt[i-1];
for(i=len;i>0;i--)sa[cnt[px[i]]--]=id[i];
memcpy(oldrk,rk,sizeof(rk));
for(p=0,i=1;i<=len;i++)rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;
}
for(register int k=0,i=1;i<=len;i++)
{
if(k)--k;
while(s[i+k]==s[sa[rk[i]-1]+k])++k;
h[rk[i]]=k;
}
int l=1,r=1000,mid;
while(l<r)
{
mid=l+r+1>>1;
if(check(mid))l=mid;
else r=mid-1;
}
if(check(r))
{
set<int> S;S.insert(belong[sa[1]]);
for(register int i=2;i<=len;i++)
{
while(h[i]>=r&&i<=len)S.insert(belong[sa[i]]),i++;
if((S.size()<<1)>n)
{
for(register int j=0;j<r;j++)putchar(s[sa[i-1]+j]);
putchar('\n');
}
S.clear();
S.insert(belong[sa[i]]);
}
}
else printf("?\n");
}
return 0;
}
```