字符串处理的经典问题
扯淡
我们有很多工具。
记录一下可以怎么用。
只介绍一般解法（通用解法）
一个串
给出一个字符串A，求本质不同的子串个数。
解法：
对A建立SAM。一个子串对应自动机上从init开始的一条路径。对这张DAG做DP，统计自动机上从init开始的路径条数即可。
令Ans[x]为从init走出的路径中，到达x的路径的数量。则有：
Ans[x]=sigma(Ans[prefix])
Ans[1]=1
时间复杂度为O(lena)。
代码：
int stk[210000<<1],Fin[210000<<1],stktop;
long long Ans[210000<<1];
long long sum;
long long Count() {
for(vi=1; vi<=cnt; vi++)for(vj=0; vj<26; vj++)if(A[vi].ne[vj])Fin[A[vi].ne[vj]]++;
stk[1]=Ans[1]=stktop=1;
while(stktop) {
vi=stk[stktop]; stk[stktop--]=0;
for(vj=0; vj<26; vj++)if(A[vi].ne[vj]) {
Ans[A[vi].ne[vj]]+=Ans[vi];
Fin[A[vi].ne[vj]]--;
if(!Fin[A[vi].ne[vj]]) {
stk[++stktop]=A[vi].ne[vj]; sum+=Ans[A[vi].ne[vj]];
}
}
}
return sum;
}
给出一个字符串A，求本质不同的第k小子串。
解法：
对A建立SAM，预处理出当前节点往后可以走出的所有子串的数量。之后我们贪心决策即可。类似于在平衡树的Rank查找。
记Sum[x]为从init走出的路径中，经过x的路径的数量。则有：
Sum[x]=sigma(Sum[next])+1
时间复杂度O(lena)。
代码：
long long Sum[210000<<1];
void DFS(int x) {
Sum[x]=1;
for(int vk=0; vk<26; vk++)if(A[x].ne[vk]) {
DFS(A[x].ne[vk]); Sum[x]+=Sum[A[x].ne[vk]];
}
}
int tmp,now,anstop;
char Ans[210000];//记录答案
void Rank(int k) {
DFS(1);
for(vi=1;;) {
/*当前询问的状态(vi,k)表示查询从init经过vi且不包含init到vi这条路径的第k小的路径*/
if(!k)break;
tmp=0;
for(vj=0; vj<26; vj++) {
last=tmp; tmp+=Sum[A[vi].ne[vj]];
if(tmp>=k) {now=vj; break;}
}
Ans[++anstop]=now+'a';
vi=A[vi].ne[now]; k-=last+1;
}
}
给出一个字符串A，求所有子串子k小的子串。
解法：
对A建立SAM，预处理当前节点的right集合的大小（即有多少init到当前节点所表示的子串出现次数），同样预处理出当前节点往后可以走出的子串数量。同样用之前思路即可。
注意在这里，终止条件有所不同。
记Size[x]=|right(x)|，Sum[x]为从init走出的路径中，经过x的路径的数量。则有：
Size[x]=sigma(Size[son])
初始状态：Size[np]=1,Size[nq]=0
Sum[x]=sigma(Sum[next])+Size[x]
时间复杂度O(lena)。
代码：
int stk[210000<<1],Fin[210000<<1];
int stktop;
void Topu() {//预处理size（right集合的大小）
for(vi=1; vi<=cnt; vi++)Fin[Fa[vi]]++;
for(vi=1; vi<=cnt; vi++)if(!Fin[vi])stk[++stktop]=vi;
while(stktop) {
vi=stk[stktop]; stk[stktop--]=0; Fin[Fa[vi]]--;
A[Fa[vi]].size+=A[vi].size;
if(!Fin[Fa[vi]]&&Fa[vi])stk[++stktop]=Fa[vi];
}
}
long long Sum[210000<<1];
void DFS(int x) {
Sum[x]=A[x].size;
for(int vk=0; vk<26; vk++)if(A[x].ne[vk]) {
DFS(A[x].ne[vk]); Sum[x]+=Sum[A[x].ne[vk]];
}
}
long long tmp,lastv;
int now,anstop;
char Ans[210000];
void Rank(long long k) {
Topu(); DFS(1); A[1].size=0;
for(vi=1;;) {
if(k<=0)break;//注意终止条件，因为下面k-=lastv+A[vi].size，k可能会变为负数
tmp=0;
for(vj=0; vj<26; vj++)if(A[vi].ne[vj]) {
lastv=tmp; tmp+=Sum[A[vi].ne[vj]];
if(tmp>=k) {now=vj; break;}
}
Ans[++anstop]=now+'a';
vi=A[vi].ne[now]; k-=lastv+A[vi].size;
}
}
给出一个字符串A，求A所有长度为k的子串中字典序最小的子串。
解法：
对A建立SAM，预处理出当前节点可以往后走的最远的步数。贪心取即可。
记Far[x]为x可以往后走的最远的步数。则有：
Far[x]=max(Far[next])+1
时间复杂度O(lena)。
代码：
int Far[210000<<1]; bool vis[210000<<1];
void DFS(int x) {
vis[x]=1;
for(int vk=0; vk<26; vk++)if(A[x].ne[vk]) {
if(!vis[A[x].ne[vk]])DFS(A[x].ne[vk]);
Far[x]=std::max(Far[x],Far[A[x].ne[vk]]);
}
Far[x]++;
}
int now,anstop; char Ans[210000];
void Run(int len) {
DFS(1); now=1;
for(vi=1; vi<=len; vi++)
for(vj=0; vj<26; vj++)if(Far[A[now].ne[vj]]>=len-vi+1) {
Ans[++anstop]=vj+'a'; now=A[now].ne[vj]; break;
}
}
给出一个字符串A，求与A循环同构的字符串中字典序最小的字符串。
解法：
对A+A建立SAM，转换为求长度为lena的字典序最小的子串。求法即可见上。
时间复杂度O(lena)。
代码：
void Build(const char *x,const int &len) {
last=cnt=1;
for(vj=1; vj<=len; vj++)Extend(x[vj]-'a');
for(vj=1; vj<=len; vj++)Extend(x[vj]-'a');
}
给出一个字符串A，求将A后缀排序之后，分别求出排名为[1..n]的后缀的起始位置以及排名第i的后缀与排名第i-1的后缀的最长公共前缀的长度。
解法一：
对A建一个SA。SA还可以求出H[i]=Height[Rank[i]]。
时间复杂度O(lenaloglena)/O(lena)。
代码：
for(int i=1; i<=n; i++)Rank[SA[i]]=i;
for(int i=1,j=0; i<=n; i++) {
int k=SA[Rank[i]-1];
if(k==0) {j=0; continue;}
if(j!=0)j--;
while(an[i+j]==an[k+j])j++;
Height[Rank[i]]=j;
}
解法二：
对A的反串建立一个SAM。得到正串的后缀树。得到后缀树上节点Fa[x]是通过那一个字符转移到的节点x。至于如何得到，可以通过下图理解：
（注意这里的pos是在原串中的位置）
而第二问，我们可以临时记录后缀树上的LCA即可。
我们令Tree[x][ch]表示x通过ch可以走到的边，maxn[x]表示x可以对应的最长的子串的长度，pos[x]表示x在原串中的位置（注意pos[nq]=pos[q]），ifs[x]表示x为np还是nq。那么有：
Tree[Fa[x]][s[maxn[Fa]+pos[x]]-'a']
ifs[np]=1,ifs[nq]=0
时间复杂度O(lena)。
代码：
void Build(const char *x,const int len) {
cnt=last=1;
for(vj=len; vj>=1; vj--)Extend(x[vj]-'a',vj);
}
int stk[110000<<1],Fin[110000<<1];
int stktop;
void Topu() {
for(vi=1; vi<=cnt; vi++)Fin[Fa[vi]]++;
for(vi=1; vi<=cnt; vi++)if(!Fin[vi])stk[++stktop]=vi;
while(stktop) {
vi=stk[stktop];
stk[stktop--]=0;
A[Fa[vi]].size+=A[vi].size;
Fin[Fa[vi]]--;
if(!Fin[Fa[vi]])stk[++stktop]=Fa[vi];
}
}
void Suf_Tree(const char *x) {
for(vi=2; vi<=cnt; vi++)Tree[Fa[vi]][x[A[Fa[vi]].maxn+A[vi].pos]-'a']=vi;
}
int top,lcplen;//lcplen记录临时的LCA所代表的最长子串的长度
int S[110000<<1],Height[110000<<1];
void Suf_sort(int x) {
if(ifs[x])S[++top]=A[x].pos,Height[top]=lcplen,lcplen=A[x].maxn;//答案是LCA的maxn，不必再求size了。
int vk;
for(vk=0; vk<26; vk++)if(Tree[x][vk])Suf_sort(Tree[x][vk]),lcplen=A[x].maxn;
}
两个串
给出两个字符串A与B，求A与B的最长公共子串。
解法：
对A建立SAM。运行B。如果可以转移则转移，令length++，反则，由于SAM上x的父亲表示子串init->x的除了x之外的后缀（因为maxn[fa[x]]=minn[x]+1），所以跳到x的父亲上，令length=A[y].maxn+1，y为第一个可以转移的x的祖先。
最终都要转移。
时间复杂度为O(lena+lenb)。
代码：
int ans,now;
int Run(char *b) {
ans=now=0; p=1;
for(vi=1; vi<=len; vi++) {
if(A[p].ne[b[vi]-'a']) {
p=A[p].ne[b[vi]-'a']; now++;
} else {
for(; p&&!A[p].ne[b[vi]-'a'];)p=pre[p];
if(!p) {
p=1; now=0;
} else {
now=A[p].maxn+1; p=A[p].ne[b[vi]-'a'];
}
}
ans=std::max(ans,now);
}
return ans;
}
给定两个字符串A与B，求B在A中出现的次数。
解法一：
对A与B做KMP即可。当匹配成功一次的时候，令匹配的指针j=next[j]，继续匹配。
时间复杂度为O(lena+lenb)。
代码：
int j=0;
for(int i=1; i<=lena; i++) {
while((bn[j+1]!=an[i])&&(j>0))j=next[j];
if(bn[j+1]==an[i])j++;
if(j==lenb) {time++;j=next[j];}
}
解法二：
对A建立SAM。求出每个状态的|right(x)|大小。运行B，终点的|right|即为答案。
时间复杂度O(lena+lenb)。
代码：
int Fin[210000<<1],stk[210000<<1];
int stktop;
void Topu() {
for(vi=1; vi<=cnt; vi++)Fin[Fa[vi]]++;
for(vi=1; vi<=cnt; vi++)if(!Fin[vi])stk[++stktop]=vi;
while(stktop) {
vi=stk[stktop]; stk[stktop--]=0; A[Fa[vi]].size+=A[vi].size; Fin[Fa[vi]]--;
if(!Fin[Fa[vi]])stk[++stktop]=Fa[vi];
}
A[0].size=A[1].size=0;
}
int now;
int Query(char *x,const int &len) {
Topu(); now=1;
for(vi=1; vi<=len; vi++)if(A[now].ne[x[vi]-'a'])now=A[now].ne[x[vi]-'a']; else return 0;
return A[now].size;
}
给出两个字符串A与B，求B在A中第一次出现的位置。
解法一：
KMP。匹配成功的时候弹出即可。
时间复杂度O(lena+lenb)。
代码：
j=0;
for(i=2; i<=lenb; i++) {
while(bn[j+1]!=bn[i]&&j)j=next[j];
if(bn[j+1]==bn[i])j++;
next[i]=j;
}
j=0;
for(i=1; i<=lena; i++) {
while(bn[j+1]!=an[i]&&j)j=next[j];
if(bn[j+1]==an[i])j++;
if(j==lenb) {printf("%d\n",i-lenb+1);return 0;}
}
解法二：
对A建立SAM。预处理出每个节点的right集合最小值。运行B，返回终点的right集合最小值即可。
记minpos[x]为x状态的right集合的最小值，则有：
minpos[x]=min(minpos[x],minpos[son])
初始状态minpos[np]=1，minpos[nq]=+none（正无穷）
代码：
int Fin[210000<<1],stk[210000<<1];
int stktop;
void Topu() {
for(vi=1; vi<=cnt; vi++)Fin[Fa[vi]]++;
for(vi=1; vi<=cnt; vi++)if(!Fin[vi])stk[++stktop]=vi;
while(stktop) {
vi=stk[stktop]; stk[stktop--]=0;
A[Fa[vi]].minpos=std::min(A[vi].minpos,A[Fa[vi]].minpos);
Fin[Fa[vi]]--; if(!Fin[Fa[vi]])stk[++stktop]=Fa[vi];
}
}
int now;
int Run(char *x,const int &len) {
Topu();
now=1;
for(vi=1; vi<=len; vi++)if(A[now].ne[x[vi]-'a'])now=A[now].ne[x[vi]-'a'];
else return 0;
return A[now].minpos-len+1;
}
多个串
给定一个主串T，多次给出字符串P，查询P是否为T的子串。
解法：
把T建立SAM。从自动机init走到一个节点就是一个子串，走到底就是一个后缀。所以如果不能转移下去了，就返回0。运行成功则返回1。
时间复杂度O(lenT+sigma(lenP))。
代码：
bool Run(char *x,const int &len) {
int p=1;
for(vj=1; vj<=len; vj++)
if(A[p].ne[x[vj]-'a'])p=A[p].ne[x[vj]-'a'];
else return 0;
return 1;
}
给出n个字符串Si，求Si的最长公共子串。
解法：
先拿一个串建立SAM。接下来那剩下的串运行。每一次运行视为两个串做LCS的结果。由于可以Fa[x]代表(init,x)的后缀，即x有的长度Fa[x]都可能有（在两个串的时候不用处理是因为对答案没有影响）。所以在做完一次之后需要在parent树上更新一次。
每一次做完之后，更新当前状态的答案，表示到当前匹配的串为止，最长的最长公共子串。
注意由于每个串最长匹配maxn个，一个串的答案还要与maxn去min。
最后答案是所有的状态的答案取max。
即，令len[x]为x状态到当前匹配的串为止，最长的最长公共子串。cur[x]为这一个串匹配的结果。maxn[x]为x状态所能接收的子串的长度。则有：
cur[x]=max(cur[x],cur[son])
len[x]=min(maxn[x],cur[x])//每一个串更新一次
ans=max(len[x])
时间复杂度O(sigma(len))。
代码：
void Build(const char *x,const int &len) {
cnt=last=1;
for(vj=1; vj<=len; vj++)Extend(x[vj]-'a');
for(vj=1; vj<=cnt; vj++)A[vj].len=A[vj].maxn;
}
int now,ch,tim;
int vis[110000<<1];
void Run(const char *x,const int &len) {
p=1; now=0;
for(vi=1; vi<=len; vi++) {
ch=x[vi]-'a';
if(!A[p].ne[ch]) {
for(; p&&!A[p].ne[ch]; p=Fa[p]);
if(!p) {now=0; p=1; continue;} else {now=A[p].maxn+1; p=A[p].ne[ch];}
} else {p=A[p].ne[ch]; now++;}
A[p].cur=max(A[p].cur,now);
}
}
int stk[110000<<1],Fin[110000<<1],stktop;
void Topu() {
for(vi=1; vi<=cnt; vi++)Fin[Fa[vi]]++;
for(vi=1; vi<=cnt; vi++)if(!Fin[vi])stk[++stktop]=vi;
while(stktop) {
vi=stk[stktop]; stk[stktop--]=0;
A[Fa[vi]].cur=max(A[Fa[vi]].cur,A[vi].cur);
Fin[Fa[vi]]--; if(!Fin[Fa[vi]])stk[++stktop]=Fa[vi];
}
for(vi=1; vi<=cnt; vi++)A[vi].len=min(A[vi].len,A[vi].cur),A[vi].cur=0;
}
int ans;
void Count() {
for(vi=1; vi<=cnt; vi++)ans=max(A[vi].len,ans);
}
for(i=2; i<=n; i++) {
D.Run(A[i],len[i]);
D.Topu();
}