后缀自动机简介与题目
后缀自动机
内容来自 回文树 - OI Wiki (oi-wiki.com) ，题目来自 回文自动机の题单 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) @ hyfhaha 。
部分题目解析直接抄的是洛谷题解
前言
和其他自动机类似，回文自动机也是由转移边和周骓链接（fail 指针）组成，每个节点都可以岱庙一个回文子串。
与manacher 需要分隔符不同，回文自动机的办法是建立两棵树，一棵树中的节点对应的回文子串长度均为奇数，另一颗树中的节点对应的回文子串的长度均为偶数。
和其他的自动机一样，一个节点的 fail 指针指向的是这个节点所代表的回文串的最长回文后缀所对应的几点，但是转移边并非代表在原节点代表的回文串后加一个字符，而是表示在原节点代表的回文串前后各加一个相同的字符。
我们还需要在每个节点上维护此节点对应回文子串的长度 len 。这个信息保证了我们可以轻松地构造出回文树。
建造
回文树由两个初始状态，分别代表长度为 \(-1,0\) 的回文串。我们可以称它们为奇根和偶根。它们不表示任何实际的字符串，仅作为初始状态存在。
偶根的 fail 指针指向奇根，而我们并不关心奇根的 fail 指针，因为奇根不可能失配（奇根转移出的下一个状态长度为 \(1\) ，即单个字符。一定是回文子串）。
考虑构造完前 \(p-1\)个字符的回文树之后，向自动机种添加在原串里位置为 \(p\) 的字符。
我们从以上一个字符结尾的最长回文子串对应的节点开始，不断沿着 fail 指针走，直到找到一个节点班组 \(s_p=s_p-len -1\) ，即满足此节点所对应回文子串的上一个字符与待假如的字符相同。
同时，长度为 \(-1\) 的节点的优势就体现出来了，如果没有一个子串能满足匹配条件就是同一个位置的 \(s_p=s_p\) ，自然就得到了这个串。
并且没有新建出来的节点的时候，就需要新建。
然后我们还需要求出新建的节点的 fail 指针。具体方法与上面的过程类似，不断跳转 fail 指针，找到最长回文后缀，将对应节点设为 fail 指针所指的对象即可。
显然，这个节点是不需要被新建的，因为回文串的另一边已经确定。
如果 fail 没有匹配到，那么将它连向长度为 \(0\) 的那个节点，着显然是可行的。（因为这是所有节点的后缀）
线性状态数证明
定理
对于一个字符串 \(s\) ，它的本质不同回文子串个数最多只有 \(|s|\) 个。
证明
考虑使用数学归纳法。
- 当 \(|s|=1\) 时， \(s\) 只有一个字符，同时也只有一个子串，并且这个子串是回文的，因此结论成立。
- 当 \(|s|>1\) 时，设 \(t=sc\) ，表示 \(t\) 为串 \(s\) 的最后添加一个字符 \(c\) 后形成的字符串，假设结论对 \(s\) 串成立。考虑以最后一个字符 \(c\) 结尾的回文子串，假设它们的左端点由小到大排序为 \(l_1,l_2,\dots,l_k\) 。由于 \(t[l_1..|t|]\) 是回文串，因此对于所有位置 \(l_1\leq p\leq |t|\) ，由 \(t[p..|t|]=t[l_1..l_1+|t|-p]\) 。所以对于 \(1
因此回文树的状态数是 \(O(|s|)\) 的。对于每种状态，它实际只代表一个本质不同的回文子串，即转移到该节点的状态唯一，因此总的转移数也是 \(O(|s|)\) 的。
正确性证明
对于上述操作，显然可以得到以下结论。（其实确实很显然，懒得写了，别问，问就是提高效率）。
假如 \(n\) 个字符，所以只会加 \(n\) 次深度，最后也只会跳 \(2n\) 次 fail 。
因此，构造 \(s\) 的回文数的时间复杂度为 \(O(|s|)\) 。
模板
P5496 【模板】回文自动机（PAM） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
给定一个字符串 \(s\) 。保证每个字符为小写字母。对于 \(s\) 的每个位置，请求出以该位置结尾的回文子串个数。
题解
上面都讲了怎么建立 PAM 了，那么怎么统计以该位结尾的回文子串个数呢。就是
sum[v]=sum[fail[v]]+1;//统计答案
...
printf("%d ",lasans=am1.sum[am1.las]);
完整代码
#include
#include
#include
using namespace std;
const int N=1000006;
struct PAM{
int ch[N][26],fail[N],len[N],sum[N];//sum[i]表示到i节点的子回文串数量
int tot,siz,las=0;
char s[N];
inline int nwnode(int l){
len[++tot]=l;
memset(ch[tot],0,sizeof(ch[tot]));
fail[tot]=0;
return tot;
}
PAM(){
tot=-1,las=0;
s[siz=0]='#';
nwnode(0);
nwnode(-1);
fail[0]=1;
}
inline int getfail(int x){
while(s[siz-len[x]-1]!=s[siz])x=fail[x];
return x;
}
inline void inser(char c){
s[++siz]=c;
int u=getfail(las);
if(!ch[u][c-'a']){
int v=nwnode(len[u]+2);
fail[v]=ch[getfail(fail[u])][c-'a'];
ch[u][c-'a']=v;
sum[v]=sum[fail[v]]+1;//统计答案
}las=ch[u][c-'a'];
}
}am1;
char s[N];
int main(){
scanf("%s",s+1);
int n=strlen(s+1),lasans=0;
for(int i=1;i<=n;++i){
s[i]=(s[i]-97+lasans)%26+97;
am1.inser(s[i]);
printf("%d ",lasans=am1.sum[am1.las]);//最后还是要用las来定位
}putchar('\n');
return 0;
}// 359ms / 62.33MB / 991B C++14 O2
应用
本质不同回文子串个数
由线性状态数的证明，容易知道一个串的本质不同回文子串个数等于回文树的状态数。（排除奇根和偶根两个状态）。
基本应用
P4555
[P4555 国家集训队]最长双回文串 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
输入长度为\(n\)的串\(S\)，求\(S\)的最长双回文子串\(T\),即可将\(T\)分为两部分\(X\)，\(Y\)，（\(|X|,|Y|≥1\)）且\(X\)和\(Y\)都是回文串。
题解
显然是一道回文自动机板题。
设 \(L[i]\) 表示以 \(i\) 号点为左端点的最长回文串 ， \(R[i]\) 表示以 \(i\) 号点为右端点的最长回文串。
\(L[i]\) 可以通过将回文串倒过来建自动机求得 ， \(R[i]\) 可以直接用原回文串建自动机求得。
最后答案为
\[Ans=max(R[i]+L[i+1]) \]代码
#include
#include
#include
using namespace std;
const int N=300005;
typedef long long ll;
struct PAM{
int tot,las,siz;
int ch[N][26],len[N],fail[N];
char s[N];
inline int nwnode(int l){
++tot;
memset(ch[tot],0,sizeof(ch[tot]));
len[tot]=l;
fail[tot]=0;
return tot;
}
PAM(){
tot=-1,las=0;
s[siz=0]='#';
nwnode(0);nwnode(-1);
fail[0]=1;//这里是偶根不行跳奇根
}
inline int getfail(int x){
while(s[siz-len[x]-1]!=s[siz])x=fail[x];
return x;
}
inline int inser(char c){
s[++siz]=c;
int u=getfail(las);
if(!ch[u][c-'a']){
int v=nwnode(len[u]+2);
fail[v]=ch[getfail(fail[u])][c-'a'];
ch[u][c-'a']=v;
}
las=ch[u][c-'a'];
return len[las];
}
}am1,am2;
char s[N];
int sml[N],smr[N],ans=0;
int main(){
scanf("%s",s+1);
int n=strlen(s+1);
for(int i=1;i<=n;++i)
sml[i]=am1.inser(s[i]);
for(int i=n;i>=1;--i)
smr[i]=am2.inser(s[i]);
for(int i=1;i 回文子串出现次数
建出回文树，使用类似的后缀自动机统计出现次数的方法。
由于回文树的构造过程中，节点本身就是按拓扑序插入，因此只需要逆序枚举所有状态，将当前状态的出现次数加到其 fail 指针对应的状态的出现次数上即可。
P3649
Loading - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
代码
#include
#include
#include
using namespace std;
const int N=300005;
typedef long long ll;
namespace PAM{
int tot,las,siz;//tot记录PAM节点的个数，siz记录已经假如字符的长度
int cnt[N],ch[N][26],len[N],fail[N];
char s[N];
inline int nwnode(int l){
++tot;
memset(ch[tot],0,sizeof(ch[siz]));
len[tot]=l;
fail[tot]=cnt[tot]=0;
return tot;
}
inline void clear(){
tot=-1,las=0;
s[siz=0]='#';
nwnode(0);
nwnode(-1);
fail[0]=1;
}
inline int getfail(int x){
while(s[siz-len[x]-1]!=s[siz])x=fail[x];
return x;
}
inline void insert(char c){
s[++siz]=c;
int u=getfail(las);
if(!ch[u][c-'a']){
int v=nwnode(len[u]+2);
fail[v]=ch[getfail(fail[u])][c-'a'];
ch[u][c-'a']=v;
}las=ch[u][c-'a'];
++cnt[las];
}
ll solve(){
ll ans=0;
for(int i=tot;i>=0;--i)
cnt[fail[i]]+=cnt[i];
for(int i=1;i<=tot;++i)
ans=max(ans,(ll)len[i]*cnt[i]);
return ans;
}
}
char s[N];
int main(){
PAM::clear();
scanf("%s",s+1);
int n=strlen(s+1);
for(int i=1;i<=n;++i)
PAM::insert(s[i]);
printf("%lld\n",PAM::solve());
return 0;
}// 78ms / 34.13MB / 1.10KB C++14 O2
LG1659
[P1659 国家集训队]拉拉队排练 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
理解了怎么统计回文子串出现次数之后就是模板题。
具体可以见代码
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=1000006;
const ll MOD=19930726;
inline ll fpr(ll b,ll t,ll tmp=1){
for(;t;t>>=1,b=b*b%MOD)
if(t&1)tmp=tmp*b%MOD;
return tmp;
}
ll bot[N];
struct PAM{
char s[N];
int tot,siz,las;
int ch[N][26],fail[N],len[N],cnt[N];
inline int nwnode(int l){
len[++tot]=l;
memset(ch[tot],0,sizeof(ch[tot]));
fail[tot]=cnt[tot]=0;
return tot;
}
PAM(){
tot=-1,las=0;
s[siz=0]='#';
nwnode(0);
nwnode(-1);
fail[0]=1;
}
inline int getfail(int x){
while(s[siz-len[x]-1]!=s[siz])x=fail[x];
return x;
}
inline void inser(char c){
s[++siz]=c;
int u=getfail(las);
if(!ch[u][c-'a']){
int v=nwnode(len[u]+2);
fail[v]=ch[getfail(fail[u])][c-'a'];
ch[u][c-'a']=v;
}las=ch[u][c-'a'];
++cnt[las];
}
inline void ready(){
for(int i=tot;i>=0;--i)
cnt[fail[i]]+=cnt[i];
for(int i=2;i<=tot;++i)
bot[len[i]]+=cnt[i];
}
}am1;
int n;
ll k,ans=1;
char s[N];
int main(){
scanf("%d%lld%s",&n,&k,s+1);
for(int i=1;i<=n;++i)
am1.inser(s[i]);
am1.ready();
for(int i=n;i>=1;--i){
if(i&1){
if(bot[i]<=k){
k-=bot[i];
ans=ans*fpr((ll)i,bot[i])%MOD;
}else{
ans=ans*fpr((ll)i,k)%MOD;
k=0;break;
}
}
}
if(k>0)puts("-1");
else printf("%lld\n",ans);
return 0;
}// 262ms / 72.52MB / 1.36KB C++14 O2
回文自动机上的2倍问题
P4762
[P4762 CERC2014]Virus synthesis - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
初始有一个空串，利用下面的操作构造给定串 \(S\) 。
- 串开头或末尾加一个字符
- 串开头或末尾加一个该串的逆串
题解
首先可以发现，操作 2 显然是越多越好。而我们发现，操作 2 之后产生了一个长度为偶数的回文串。由于不能拼接，最终答案一定是在一个长度为偶数的回文串基础上暴力添加得到的。
于是考虑建立 PAM ，设 \(f_x\) 表示产生节点 \(x\) 代表的回文串的最小操作步数，\(l_x\) 代表节点 \(x\) 代表的回文串的长度，那么最终答案即为 \(\min\{f_x+n-l_x\}\) 。
对于转移，首先可以发现，对于节点 \(x\) 对应的一个长度为偶数且不为 \(0\) 的回文串，如果在它两边添加一个相同的字符，可以得到节点 \(v\) 对应的回文串（相当于 PAM 上的一条边），那么 \(f_v=\min(f_v,f_x+1)\)
然后我们可以发现，一个回文串也可以通过操作 \(2\) 获得。于是我们维护一个 \(hf\) 指针，代表这个串最长的且长度不超过该串长度的一半的回文串所对应的节点。而这可以在插入时顺便求出，这里就不再讲了。
设 \(hf_x=p\) ，可以得到转移：\(f_x=\min(f_x,f_p+\dfrac{l_x}{2}-l_p+1)\)。
代码
#include
#include
#include
#include
#include P4287
[P4287 SHOI2011]双倍回文 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
记字符串\(w\)的倒置为\(w^R\)。
对字符串x，如果\(x\)满足\(x^R=x\)，则称之为回文。
如果x能够写成的\(ww^Rww^R\)形式，则称它是一个“双倍回文”。换句话说，若要\(x\)是双倍回文，它的长度必须是\(4\)的倍数，而且\(x\)，\(x\)的前半部分，\(x\)的后半部分都要是回文。
求最长的双倍回文串。
题解
用上一题同样的方法可求出 \(hf\) 指针，即某一状态的字符串中的长度小于 \(len\div2\) 的回文子串的状态位置。
那么如果 \(len_{hf_i}\times 2=len_i\) 且 \(len_i\bmod 4=0\) 那么即满足为双倍回文。
代码
#include
#include
#include
using namespace std;
const int N=1000006;
struct PAM{
char s[N];
int tot,siz,las;
int ch[N][26],fail[N],len[N],hf[N];
inline int nwnode(int l){
len[++tot]=l;
memset(ch[tot],0,sizeof(ch[tot]));
fail[tot]=0;
return tot;
}
PAM(){
tot=-1,las=0;
s[siz=0]='#';
nwnode(0);
nwnode(-1);
fail[0]=1;
}
inline int getfail(int x){
while(s[siz-len[x]-1]!=s[siz])x=fail[x];
return x;
}
inline void inser(char c){
s[++siz]=c;
int u=getfail(las);
if(!ch[u][c-'a']){
int v=nwnode(len[u]+2);
fail[v]=ch[getfail(fail[u])][c-'a'];
ch[u][c-'a']=v;
if(len[v]<=2)hf[v]=fail[v];//题目特色
else{
int tmp=hf[u];
while(s[siz-len[tmp]-1]!=s[siz]||((len[tmp]+2)*2)>len[v])tmp=fail[tmp];
hf[v]=ch[tmp][c-'a'];
}
}las=ch[u][c-'a'];
}
inline int solve(){//题目特色
int ans=0;
for(int i=2;i<=tot;++i)
if(len[hf[i]]*2==len[i]&&len[i]%4==0)//非常好理解
ans=max(ans,len[i]);
return ans;
}
}am1;
int n;
char s[N];
int main(){
scanf("%d%s",&n,s+1);
for(int i=1;i<=n;++i)
am1.inser(s[i]);
//puts("114514");
printf("%d\n",am1.solve());
return 0;
}// 119ms / 63.54MB / 1.45KB C++14 O2
公共回文子串数量
如标题，给出两个字符串，求出公共回文子串的数量
[P5685 JSOI2013]快乐的 JYY - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
方法一
可以直接对两个串同时建立\(\rm PAM\)。考虑\(\rm PAM\)里面每个节点的意义，节点=回文串，所以考虑我们对两个\(\rm PAM\)同时开始\(\sf dfs\)，因为起始状态相同，那么如果遇到相同的转移就说明有相同的状态，把\(sz_x\times sz_y\)作为贡献加到答案里面即可。
注意到，对于回文串之间的转移而言，由于从奇数长度只能转移到奇数长度，偶数长度只能转移到偶数长度，所以要把每一组根都 \(\sf dfs\) 一遍。
并且显然我们要特判掉虚根（即奇根和偶根）。
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=1000006;
int n,m;
ll ans;
struct PAM{
char s[N];
int tot,siz,las;
int ch[N][26],fail[N],len[N],cnt[N];
inline int nwnode(int l){
len[++tot]=l;
memset(ch[tot],0,sizeof(ch[tot]));
fail[tot]=cnt[tot]=0;
return tot;
}
PAM(){
tot=-1,las=0;
s[siz=0]='#';
nwnode(0);
nwnode(-1);
fail[0]=1;
}
inline int getfail(int x){
//printf("getfail %d\n",x);
while(s[siz-len[x]-1]!=s[siz])x=fail[x];
return x;
}
inline void inser(char c){
s[++siz]=c;
int u=getfail(las);
if(!ch[u][c-'A']){
int v=nwnode(len[u]+2);
fail[v]=ch[getfail(fail[u])][c-'A'];
ch[u][c-'A']=v;
}las=ch[u][c-'A'];
++cnt[las];
}
inline void solve(){
for(int i=tot;i>=0;--i)
cnt[fail[i]]+=cnt[i];
}
}am1,am2;
char s[N],t[N];
void dfs(int l1,int l2){
if(l1+l2>2)ans+=(ll)am1.cnt[l1]*am2.cnt[l2];//不是奇根或偶根
for(int i=0;i<26;++i){
if(am1.ch[l1][i]&&am2.ch[l2][i])
dfs(am1.ch[l1][i],am2.ch[l2][i]);
}
}
int main(){
scanf("%s%s",s+1,t+1);
n=strlen(s+1),m=strlen(t+1);
for(int i=1;i<=n;++i)am1.inser(s[i]);
for(int i=1;i<=m;++i)am2.inser(t[i]);
am1.solve(),am2.solve();
dfs(1,1);dfs(0,0);
printf("%lld\n",ans);
return 0;
}// 113ms / 29.34MB / 1.29KB C++14 O2
方法二
[P5685 JSOI2013]快乐的 JYY 题解 - ctldragon 的博客 - 洛谷博客 (luogu.com.cn)
可以直接上 广义\(PAM\) （应该可以这么叫吧），把两个字符串建到一个 广义\(PAM\) ，然后 \(dfs\) 所有节点统计答案。
能建 广义\(PAM\) 的理由：
\(PAM\) 中是专门判了重节点，况且 \(PAM\) 中没有节点会同时包含两个状态，所以可以每次都是从头加字符串，这样不会影响 \(PAM\) 的性质。构造 广义\(PAM\) 的方法和构造 广义\(SAM\) 的那个假掉的做法一样。
设 \(f[x][0]\) 是 \(A\) 串在 \(x\) 节点上的回文子串数，\(f[x][1]\) 是 \(B\) 串在 \(x\) 节点上的回文子串数。
那么答案即为 \(\large \sum\limits_{i=2}^{cnt}f[x][0]\times f[x][1]\) 。（ \(cnt\) 是节点数，0和1是根）
#include
#define pc(x) putchar(x)
#define ll long long
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){f=ch=='-'?-1:f;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
void write(ll x)
{
if(x<0){x=-x;putchar('-');}
if(x>9)write(x/10);
putchar(x%10+48);
}
int n,m,f[100005][2];ll ans;
char s[50005];
struct G_PAM
{
int ch[26],fa,len;
}tr[100005];
int lst,cnt=1;
void init()
{
s[0]=-1;tr[1].len=-1;
tr[0].fa=tr[1].fa=1;
lst=0;
}
void insert(int k,int c,int id)
{
int p=lst;
while(s[k-tr[p].len-1]!=c+'A')p=tr[p].fa;
if(!tr[p].ch[c])
{
int q=lst=++cnt,v=tr[p].fa;
while(s[k-tr[v].len-1]!=c+'A')v=tr[v].fa;
tr[q].fa=tr[v].ch[c];
tr[tr[p].ch[c]=q].len=tr[p].len+2;
}else lst=tr[p].ch[c];
f[lst][id]++;
}
vectore[600005];
void dfs(int x)
{
for(int i=0;i<(int)e[x].size();++i)
{
int y=e[x][i];dfs(e[x][i]);
f[x][0]+=f[y][0];f[x][1]+=f[y][1];
}
if(x==1||x==0)return;
ans+=1ll*f[x][0]*f[x][1];
}
int main()
{
scanf("%s",s+1);n=strlen(s+1);init();
for(int i=1;i<=n;++i)insert(i,s[i]-'A',0);
scanf("%s",s+1);n=strlen(s+1);init();
for(int i=1;i<=n;++i)insert(i,s[i]-'A',1);
for(int i=2;i<=cnt;++i)e[tr[i].fa].push_back(i);
e[1].push_back(0);dfs(1);write(ans),pc('\n');
return 0;
}
双倍经验 P5555 秩序魔咒 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
和上面那题本质相同，统计答案如下：
queueq;
q.push(make_pair(0,0));
q.push(make_pair(1,1));
while(!q.empty()){//和LG5685本质是一样的
int l1=q.front().first,l2=q.front().second;q.pop();
for(int i=0;i<26;++i){
if(am1.ch[l1][i]&&am2.ch[l2][i]){
int tmp=am1.len[am1.ch[l1][i]];//这是这个状态下公共回文子串的长度
if(tmp>anl){anl=tmp,ans=1;}
else if(tmp==anl)++ans;
q.push(make_pair(am1.ch[l1][i],am2.ch[l2][i]));
}
}
}printf("%d %d\n",anl,ans);
最小回文划分
给定一个字符串 \(s(1\leq |s|\leq 10^5)\) ，求最小的 \(k\) ，使得存在 \(s_1,s_2,\dots s_k\) ，满足 \(s_i(1\leq i\leq k)\) 均为回文串，且 \(s_1,s_2,\dots,s_k\) 依次连接后得到的字符串等于 \(s\)
考虑动态规划，记 \(dp[i]\) 表示 \(s\) 长度为 \(i\) 的前缀的最小划分数，转移只需要枚举以第 \(i\) 个字符结尾的所有回文串
\[dp[i]=1+\min\limits_{s[j+1..i]为回文串}dp[j] \]由于一个字符串最多会有 \(O(n^2)\) 个回文子串，因此上述算法的时间复杂度为 \(O(n^2)\) ，为了优化转移过程，下面给出一些引理。
相关引理
- 周期：若 \(0
- border：若 \(0\leq r<|s|\) ，\(pre(s,r)=suf(s,r)\) ，就称 \(pre(s,r)\) 是 \(s\) 的 border
周期和 border 的关系：\(t\) 是 \(s\) 的 border，当且仅当 \(|s|-|t|\) 是 \(s\) 的周期。
证明感觉非常显然（略）
引理1： \(t\) 是回文串 \(s\) 的后缀，\(t\) 是 \(s\) 的 border 当且仅当 \(t\) 是回文串
证明感觉非常显然
引理2： \(t\) 是回文串 \(s\) 的 border ( \(|s|\leq 2|t|\) ) ，\(s\) 是回文串当且仅当 \(t\) 是回文串
证明感觉比较显然，需要注意的是这里 \(|t|\) 的范围。
引理3：\(t\) 是回文串 \(s\) 的 border ，则 \(|s|-|t|\) 为 \(s\) 的最小周期，当且仅当 \(t\) 是 \(s\) 的最长回文真后缀。
证明感觉比较显然。
引理4： \(x\) 是一个回文串， \(y\) 是 \(x\) 的最长回文真后缀，\(z\) 是 \(y\) 的最长回文真后缀。令 \(u,v\) 分别为满足 \(x=uy,\,y=vz\) 的字符串，则有下面三条性质
- \(|u|\geq|v|\)
- 如果 \(|u|>|v|\) ，那么 \(|u|>|z|\) ；
- 如果 \(|u|=|v|\) ，那么 \(u=v\) 。
证明：
- （感觉比较显然），由引理 \(3\) 的推论 \(|u|=|x|-|y|\) 是 \(x\) 的最小周期，\(|v|=|y|-|z|\) 是 \(y\) 的最小周期。考虑反证法，假如 \(|u|<|v|\) ，因此 \(y\) 是 \(x\) 的后缀，所以 \(u\) 既是 \(x\) 的周期，也是 \(y\) 的周期，而 \(|v|\) 是 \(y\) 的最小周期，矛盾。所以 \(|u|\geq |v|\)
- 因为 \(y\) 是 \(x\) 的 border ，所以 \(v\) 是 \(x\) 的前缀，设字符串 \(w\) ，满足 \(x=vw\) （如下图所示），其中 \(z\) 是 \(w\) 的 border 。考虑反证法，假设 \(|u|\leq|z|\) ，那么 \(|zu|\leq 2|z|\) ，所以由引理 \(2\) ，\(w\) 是回文串，由引理 \(1\) ，\(w\) 是 \(x\) 的 border，又因为 \(|u|>|v|\) ，所以 \(|w|>|y|\) ，矛盾，所以 \(|u|>|z|\)
- \(u,v\) 都是 \(x\) 的前缀，\(|u|=|v|\) ，所以 \(u=v\)
推论：\(s\) 的所有回文后缀按照长度排序后，可以划分成 \(\log |s|\) 段等差数列
证明：（看起来很长，其实并没有那么难理解）设 \(s\) 的所有回文后缀长度从小到大排序为 \(l_1,l_2,\dots l_k\) 。对于任意 \(2\leq i\leq k-1\) ，若 \(l_i-l_{i-1}=l_{i+1}-l_i\) ，则 \(l_{i-1},l_i,l_{i+1}\) 构成一个等差数列。否则 \(l_i-l_{i-1}\neq l_{i+1}-l_i\) ，由引理 \(4\) ，有 \(l_{i+1}-l_i>l_i-l_{i-1}\) ，且 \(l_{i+1}-l_i>l_{i-1}\) ，\(l_{i+1}>2l_{i-1}\) 。因此，若相邻两队回文后缀的长度之差发生变化，那么这个最大长度一定会相对于最小长度翻一倍。显然，长度翻倍最多只会发生 \(O(\log |s|)\) 次，也就是 \(s\) 的回文后缀长度可以划分成 \(\log |s|\) 段等差数列。
优化
有了上面的结论后，现在可以考虑如何优化 \(dp\) 的转移。
回文树上的每个节点 \(u\) 需要多维护两个信息， \(diff[u]\) 和 \(slink[u]\) 。 \(diff[u]\) 表示节点 \(u\) 和 \(fail[u]\) 所代表的回文串的长度差，即 \(len[u]-len[fail[u]]\) 。 \(slink[u]\) 表示 \(u\) 一直沿着 \(fail\) 向上跳到第一个节点 \(v\) ，使得 \(diff[v]\neq diff[u]\) 吗，也就是 \(u\) 所在等差数列中长度最小的那个节点。
根据上面证明的结论，如果使用 \(slink\) 指针向上跳的话，每向后添加一个字符，只需要向上跳 \(O(\log |s|)\) 次。依次，可以考虑将一个等差数列表示的所有字符串的 \(dp\) 值hi和（在原问题总指 \(\min\) ），记录到最长的哪一个回文串对应节点上。
\(g[v]\) 表示 \(v\) 所在等差数列的 \(dp\) 值之和，且 \(v\) 是这个等差数列中长度最长的节点，则 \(g[v]=\sum_{x,slink[x]=v}dp[i-len[x]]\) 这里 \(i\) 是当前枚举到的下标。
下面我们考虑如何更新 \(g\) 数组和 \(dp\) 数组。以下图为例，假设当前枚举到第 \(i\) 个字符，回文数上对应的节点为 \(x\) 。 \(g[x]\) 为橙色三个位置的 \(dp\) 值之和（最短的回文串 \(slink[x]\) 算在下一个等差数列中）。\(fail[x]\) 上一次出现位置是 \(i-diff[x]\) （在 \(i-diff[x]\) 处结束），\(g[fail[x]]\) 包含的 \(dp\) 值是蓝色位置。因此，\(g[x]\) 实际上等于 \(g[fail[x]]\) 和多出来一个位置的 \(dp\) 值之和，多出来的位置是 \(i-(len[slink[x]]+diff[x])\) 。最后再用 \(g[x]\) 去更新 \(dp[i]\) ，这部分等差数列的贡献就计算完毕了，不断跳 \(slink[x]\) ，出伏这个过程即可。具体实现方式可参考例题代码。
最后，上述做法的正确性依赖于：如果 \(x\) 和 \(fail[x]\) 属于同一个等差数列，那么 \(fail[x]\) 上一次出现的位置是 \(i-diff[x]\) 。
证明：
根据引理 \(1\) ，\(fail[x]\) 是 \(x\) 的 border，因此其在 \(i-diff[x]\) 处出现。
假设 \(fail[x]\) 在 \((i-diff[x],i)\) 中的 \(j\) 位置出现。由于 \(x\) 和 \(fail[x]\) 属于同一个等差数列，那么 \(fail[x]\) 上一次出现位置是 \(i-diff[x]\) 。
例题
Problem - 932G - Codeforces
给定一个字符串 \(s\) ，要求将 \(s\) 划分为 \(t_1,t_2,\dots,t_k\) ，其实 \(k\) 是 \(t_i=t_{k-i+1}\) ，求这样的划分方案数。
题解
构造字符串 \(t=s[0]s[n-1]s[2]s[n-3]\dots s[\frac{n}{2}-1]s[\frac{n}{2}]\) ，我呢提等价于求 \(t\) 的偶回文划分方案数，把上面的转移方程改成求和形式并且只在偶数位置更新 \(dp\) 数组即可。时间复杂度 \(O(n\log n)\) ，空间复杂度为 \(O(n)\)
代码
#include
#include
#include
using namespace std;
typedef long long ll;
const int MOD=1000000007,N=1000006;
struct PAM{
int s[N];
int tot,siz,las;
int ch[N][26],fail[N],len[N],dif[N],slink[N];
inline nwnode(int l){
len[++tot]=l;
memset(ch[tot],0,sizeof(ch[tot]));
fail[tot]=0;
return tot;
}
PAM(){
tot=-1,las=0;
s[siz=0]='#';
nwnode(0);
nwnode(-1);
fail[0]=1;
}
inline int getfail(int x){
while(s[siz-len[x]-1]!=s[siz])x=fail[x];
return x;
}
inline void inser(char c){
s[++siz]=c;
int u=getfail(las);
if(!ch[u][c-'a']){
int v=nwnode(len[u]+2);
fail[v]=ch[getfail(fail[u])][c-'a'];
ch[u][c-'a']=v;
dif[v]=len[v]-len[fail[v]];
if(dif[v]==dif[fail[v]])
slink[v]=slink[fail[v]];
else slink[v]=fail[v];//不满足等差数列，直接赋成现在的fail
}
las=ch[u][c-'a'];
}
}am;
int n;ll dp[N],g[N];
char s[N],t[N];
int main(){
scanf("%s",s+1);
n=strlen(s+1);
for(int i=1,p=0;i<=n;++i)
t[++p]=s[i],t[++p]=s[n-i+1];
dp[0]=1;
for(int i=1;i<=n;++i){
am.inser(t[i]);
for(int x=am.las;x>1;x=am.slink[x]){
g[x]=dp[i-am.len[am.slink[x]]-am.dif[x]];
if(am.dif[x]==am.dif[am.fail[x]])g[x]=(g[x]+g[am.fail[x]])%MOD;
if(i%2==0)dp[i]=(dp[i]+g[x])%MOD;
}
}printf("%lld\n",dp[n]);
return 0;
}
Problem - CF906E - Codeforces
题意
给两个长度相同的串 \(A,B\)，允许翻转 \(A\) 的任意个子区间，求翻转最少次数使得 \(A\) 与 \(B\) 相等并求出方案。\(|A|,|B|\le5\times 10^5\).
题解
构造 \(C=a_1b_1a_2b_2...a_nb_n\)。我们首先想如果翻转了 \(A\) 中的 \([l,r]\) 意味着 \(a_l=b_r,a_{l+1}=b_{r-1}...\)，所以在 \(C\) 中 \(a_lb_la_{l+1}b_{l+1}...a_rb_r\) 这段区间是回文的，则问题转化为偶回文子串划分问题，可以参考上题。
时间复杂度 \(O(n\log n)\)。
代码
#include
#include
#include
typedef long long ll;
using namespace std;
const int N=1000006;
int n;
int dp[N],g[N],pre[N];
struct PAM{
int s[N];
int siz,tot,las;
int fail[N],ch[N][26],len[N],dif[N],slk[N];
inline int nwnode(int l){
len[++tot]=l;
memset(ch[tot],0,sizeof(ch[tot]));
fail[tot]=0;
return tot;
}
PAM(){
tot=-1,las=0;
s[siz=0]=-1;
nwnode(0);
nwnode(-1);
fail[0]=1;
}
inline int getfail(int x){
while(s[siz-len[x]-1]!=s[siz])x=fail[x];
return x;
}
inline void inser(int c){
s[++siz]=c;
int u=getfail(las);
if(!ch[u][c]){
int v=nwnode(len[u]+2);
fail[v]=ch[getfail(fail[u])][c];
ch[u][c]=v;
dif[v]=len[v]-len[fail[v]];
if(dif[v]==dif[fail[v]])
slk[v]=slk[fail[v]];
else slk[v]=fail[v];
}las=ch[u][c];
}
inline void solve(){
if(siz%2==0&&s[siz]==s[siz-1]&&dp[siz]>dp[siz-2])
dp[siz]=dp[siz-2],pre[siz]=siz-2;
for(int x=las;x;x=slk[x]){
g[x]=siz-len[slk[x]]-dif[x];
if(dif[fail[x]]==dif[x]&&dp[g[x]]>dp[g[fail[x]]])
g[x]=g[fail[x]];
if(siz%2==0&&dp[siz]>dp[g[x]]+1)
dp[siz]=dp[g[x]]+1,pre[siz]=g[x];
}
}
}am;
char s1[N],s2[N],s[N*2];
int main(){
scanf("%s%s",s1+1,s2+1);
n=strlen(s1+1);
for(int i=1;i<=n;++i){
//printf("%c%c",s1[i],s2[i]);
s[i*2-1]=s1[i],s[i*2]=s2[i];
}
n*=2;
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;++i){
am.inser(s[i]-'a');
am.solve();
}
if(dp[n]>=0x3f3f3f3f)return puts("-1"),0;
printf("%d\n",dp[n]);
for(int i=n;i>=1;i=pre[i]){
if(i-pre[i]>2)
printf("%d %d\n",pre[i]/2+1,i/2);
}
return 0;
}// 1.33s / 133.78MB / 1.62KB C++14 O2
一些变换
邻接链表PAM
CF17E Palisection - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
给定一个长度为 \(n(1\leq n\leq 2\times 10^6)\) 的小写字母串。问你有多少对相交的回文子串（包含也算相交） 。空间
128MB
一般的PAM写法是空间过不了了，因为对于每个节点，都要用一个大小为 \(26\) 个 int 的数组记录它的子节点。
考虑用链式前向星存储一个节点的子节点。
cstar edge[N];int head[N],cne;
inline void addline(int u,int v,int w)//链式前向星建图
{edge[++cne]=(cstar){head[u],v,w},head[u]=cne;}
inline int ch(int u,int w){//即查找ch[u][w]的编号是多少
for(int i=head[u];i;i=edge[i].next){
if(edge[i].weight==w)
return edge[i].to;
}return 0;
}
在这里，一条 \(u\) 向 \(v\) 的权值为 \(w\) 的边，表示状态 \(u\) 的回文串左右新加字符 \(w\) 得到的状态为 \(v\) 。
然后只需要将 inser 操作中的
ch[u][c]=v;改成addline(u,v,c);fail[v]=ch[getfail(fail[u])][c-'a'];改成fail[v]=ch(getfail(fail[u]),c);
回归本题
我们设用回文串的总数是 \(sum\) \(\Rightarrow ans={sum\choose 2}- 没有交集的回文串对数\) 。
考虑怎么算没有交集的回文串对数
我们考虑答案可以是 \(\sum_i\) 以\(i\)结尾的回文串个数\(\times i\)后面的回文串个数
以 \(i\) 结尾的回文串个数就是 \(i\) 这个点在 \(fail\) 树上的深度
考虑把串反过来,再用后缀和优化一下就可以了
完整代码
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=2000006,MOD=51123987;
struct cstar{int next,to,weight;};
struct PAM{
int siz,tot,las;
int fail[N],len[N],cnt[N],dep[N];
int s[N];
cstar edge[N];int head[N],cne;
inline void addline(int u,int v,int w)//链式前向星建图
{edge[++cne]=(cstar){head[u],v,w},head[u]=cne;}
inline int ch(int u,int w){//即查找ch[u][w]的编号是多少
for(int i=head[u];i;i=edge[i].next){
if(edge[i].weight==w)
return edge[i].to;
}return 0;
}
inline int nwnode(int l){
len[++tot]=l;
head[tot]=0;//本质上就是将之前挂在这个链上的边清空
fail[tot]=cnt[tot]=0;
return tot;
}
inline void init(){//这里的写法尽量和普通PAM保持一致
cne=0;//别忘了这里清空
tot=-1,las=0;
s[siz=0]=-1;
nwnode(0);nwnode(-1);
fail[0]=1;
}
inline int getfail(int x){//和一般的PAM没什么区别
while(s[siz-len[x]-1]!=s[siz])x=fail[x];
return x;
}
inline int inser(int c){//之前已经将字符转化成一个数
s[++siz]=c;
int u=getfail(las);
if(!ch(u,c)){
int v=nwnode(len[u]+2);
fail[v]=ch(getfail(fail[u]),c);
addline(u,v,c);//建边
dep[v]=dep[fail[v]]+1;
}las=ch(u,c);
++cnt[las];
return dep[las];//以i结尾的回文串个数就是i这个点在fail树上的深度
}
inline ll getall(){//统计所有的回文串个数
ll tmp=0;
for(int i=tot;i>=2;--i){
tmp=(tmp+cnt[i])%MOD;
cnt[fail[i]]+=cnt[i];
}return tmp;
}
}am;
int n;char s[N];
ll sumr[N],ans,all;
int main(){
scanf("%d%s",&n,s+1);
am.init();
for(int i=n;i>=1;--i)
sumr[i]=(sumr[i+1]+am.inser(s[i]-'a'))%MOD;
am.init();
for(int i=1;i<=n;++i)//计算没有交集的回文串的数量
ans=(ans+(ll)am.inser(s[i]-'a')*sumr[i+1]%MOD)%MOD;
all=am.getall();
printf("%lld\n",(all*(all-1)/2%MOD-ans+MOD)%MOD);
return 0;
}
//自己写的邻接PAM，嘿嘿