马拉车算法是求最长回文串的算法,其核心在于减少了冗余的重复计算,利用当前已知的数据尽可能的推出之后的数据,从而达到线性的复杂度。
我认为这个算法的核心之处是充分利用了回文串的对称性。
首先是处理回文串的一个小技巧,对于奇偶回文串,我们只需要在相邻的两个字符之间加上一个 '#' 字符,那么无论是奇串还是偶串,都会变成奇串(自行模拟)。
对于你目前已经求出的回文串 \([1,mx]\),定义 \(mid\) 为这个串的回文中心,p[i]
数组表示以 \(i\) 为回文中心的最长的回文半径。
首先给出一个结论,以 \(i\) 为回文中心的字符串的最长回文串的长度会等于 p[i]-1
,因为要减去一个 '#'。
那么怎么进行 \(manacher\) 呢?
对于一个 \(i(mid<i<mx)\),这时根据对称性,\(i\) 的对称点 \(i'\) 点为 \(mid*2-i\),那么以 \(i\) 为回文中心的最长回文半径一定不会小于以 \(i'\) 点为回文中心的最长回文半径,所以我们可以先让 p[i]=min(p[mid*2-i],mx-i)
(注意,回文半径的长度不能超过 \(mx-i\)),然后在暴力一个一个判断出 \(i\) 超过 \(mx\) 范围的回文串,并且更新 \(mx\) 和 \(mid\),反复如此,终可求矣。
如果 \(i(mx<i)\) 呢?就直接考虑暴力求了,然后再更新 \(mx\) 和 \(mid\)。
#include<bits/stdc++.h> using namespace std; const int N=3e7+5; int cnt,p[N],ans; char s[N]; void read(char *str){ char ch=getchar(); str[0]='@'; while(ch>='a'&&ch<='z') str[++cnt]='#',str[++cnt]=ch,ch=getchar(); str[++cnt]='#'; } int main(){ read(s); int mid=1,mx=1; for(int i=1;i<cnt;i++){ if(i<mx){ p[i]=min(p[(mid<<1)-i],mx-i); } else p[i]=1; while(s[i-p[i]]==s[i+p[i]]) p[i]++; if(mx<i+p[i]){ mx=i+p[i]; mid=i; } ans=max(ans,p[i]-1); } printf("%d",ans); return 0; }
最小表示法就是对于一个字符串,求她的循环同构的字符串的最小的那个。
如字符串 "gfedcba"
,她的循环同构的字符串为:
"agfedcb"
,"bagfedc"
,"cbagfed"
,"dcbagfe"
,"edcbagf"
,"fedcbag"
那么很显然,对于她来说,她的最小表示法为 "agfedcb"
。
考虑怎么来求一个字符串的最小表示法
注:这里存字符串从 \(0\) 开始存。
我们定义两个指针 \(i\) 和 \(j\),分别指向字符串 \(s\) 中的两个不同的位置(指向位置相同时就无意义了),定义当前分别从 \(i\),\(j\) 开始已经匹配了 \(k\) 个字符(从 \(i\) ,\(j\) 开始,包括 \(i\),\(j\) 本身的后 \(k\) 个字符相等)。
那么对于 s[(i+k)%n]
和 s[(j+k)%n]
:
如果相等那么匹配数 k++
;
如果 s[(i+k)%n]>s[(j+k)%n]
,则说明 \(i\sim i+k\) 之间的字符都不会作为最小表示法的开头,所以 \(i\) 直接跳到 \(i+k+1\);
如果 s[(i+k)%n]<s[(j+k)%n]
,同理可得 \(j\) 跳到 \(j+k+1\)。
最后,\(i\) 和 \(j\) 位置最小的点就是最小表示法的开头点,记为 \(ans\)。最后输出 s[(i+ans)%n]
就好了。
有一点要注意的,就是 \(i\) 不能等于 \(j\),因为要指向不同的位置,否则将会一直匹配,所以相等时让 i++
就好了。
#include<bits/stdc++.h> using namespace std; inline int read(){ int ans=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-') f=-f;ch=getchar();} while(isdigit(ch)){ans=(ans<<3)+(ans<<1)+ch-48;ch=getchar();} return ans*f; } const int N=3e5+5; int n,ans; int s1[N]; int minshow(){ int i=0,j=1,k=0; while(i<n&&j<n&&k<n){ if(s1[(i+k)%n]==s1[(j+k)%n]) k++; else{ if(s1[(i+k)%n]>s1[(j+k)%n]) i+=k+1; else j+=k+1; if(i==j) i++; k=0; } } return min(i,j); } int main(){ n=read(); for(int i=0;i<n;i++){ s1[i]=read(); } ans=minshow(); for(int i=0;i<n;i++){ printf("%d ",s1[(i+ans)%n]); } return 0; }
激动人心的 看毛片 算法来了
KMP算法核心处也是减少重复冗余的计算。
朴素算法就是双指针一个一个匹配,当有一个失配后,就将模式串从头开始匹配。复杂度可以被卡到 \(O (nm)\)
KMP失配后不是从头开始,而是利用一个 kmp[j]
数组,记录 \(j+1\) 失配后 \(j\) 应该从哪里开始重新匹配 。并且很容易发现,文本串的指针只增不减,模式串的指针会减少也会增加(因为每次失配后只用改变模式串指针位置就好了)。
上图:
此时 a[i]!=b[j+1]
失配。
于是我们将 \(j\) 从 \(4\) 移动到 \(2\) 的位置,重新开始匹配,就避免了从头开始匹配。
我们先假设我们已经求出了 kmp
数组,那么对于这个问题就很简单了。
我们只用双指针依次匹配,当失配后令模式串指针 j=kmp[j]
,再与文本串重新匹配。
代码如下:
j=0; for(int i=1;i<=lena;i++){ while(j&&a[i]!=b[j+1]) j=kmp[j];//如果不匹配,模式串就往前跳 if(a[i]==b[j+1]) j++;//如果相等就匹配下一位 if(j==lenb){//找到相同的串后输出起始位置 printf("%d\n",i-lenb+1); j=kmp[j];//跳回去 } }
因为要让指针跳回的尽可能少,所以我们就要让 kmp[j]
数组存的可以跳回的点尽可能大,所以我们就可以让 kmp[j]
数组为从 \(1 \sim j-1\) 位中,前缀和后缀相等的部分的最长长度是多少。这样就可以让指针每次跳回的尽可以少。
那么怎么求出 kmp[j]
数组呢?
其实就是用模式串对模式串自己做KMP操作
引用 Matrix67 Blog 中的巧妙证明就是
代码如下:
j=0; for(int i=2;i<=lenb;i++){ while(j&&b[i]!=b[j+1]) j=kmp[j]; if(b[i]==b[j+1]) j++; kmp[i]=j; }
复杂度如何证明?
引用 \(rqy\) 大佬的证明
每次位置指针 \(i++\) 时,失配指针 \(j\) 至多增加一次,所以 \(j\) 至多增加 \(len\) 次,从而至多减少 \(len\) 次,所以就是 \(\Theta(len_N + len_M) = \Theta(N + M)\) 的。
至此,我们结束了看毛片算法
#include<bits/stdc++.h> using namespace std; const int N=1e6+5; char a[N],b[N]; int lena,lenb; int kmp[N],j; int main(){ cin>>a+1; cin>>b+1; lena=strlen(a+1),lenb=strlen(b+1); j=0; for(int i=2;i<=lenb;i++){ while(j&&b[i]!=b[j+1]) j=kmp[j]; if(b[i]==b[j+1]) j++; kmp[i]=j; } j=0; for(int i=1;i<=lena;i++){ while(j&&a[i]!=b[j+1]) j=kmp[j]; if(a[i]==b[j+1]) j++; if(j==lenb){ printf("%d\n",i-lenb+1); j=kmp[j]; } } for(int i=1;i<=lenb;i++) printf("%d ",kmp[i]); return 0; }
AC自动机,全称"Aho_Corasick_Automaton"
,用于求解多个模式串匹配一个文本串的问题。联想到之前的学过的算法,发现有一个KMP算法(看毛片)可以求解一个模式串匹配一个文本串的问题,那么利用OI的基本思想之一的 x套x
思想,是不是可以考虑把两个算法结合起来,以达到一种神奇的效果呢?
我们发现,对于多个模式串,我们可以建一棵 \(trie\) 树方便求出他们的公共前缀,然后就可以在 \(trie\) 树上面看毛片KMP了!
众所周知,KMP最重要的是失配数组 fail
,那我们怎么在 \(trie\) 树上求 fail
数组呢?
很简单,只用跑一边 \(bfs\) 就好了,逻辑很明了看看代码就会了,不再赘述。注意优化!
void build(){ for(int i=0;i<26;i++) if(trie[0][i]) fail[trie[0][i]]=0,q.push(trie[0][i]); while(!q.empty()){ int u=q.front();q.pop(); for(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];//优化,没有这条边的时候早晚要跳回去,还不如现在跳 } } }
有了 \(fail\) 数组,那么怎么匹配呢?
也很简单,我们只用遍历,枚举一条当前文本串字符连向的边,然后把这些点的 \(fail\) 全部跑一边,然后答案直接加上结束标记 \(end\)。注意不要重复计算,用完的标记要丢掉!
int query(char *str){ int len=strlen(str),p=0,res=0; for(int i=0;i<len;i++){ p=trie[p][str[i]-'a']; for(int t=p;t&&end[t]!=-1;t=fail[t]) res+=end[t],end[t]=-1; } return res; }
最后,注意常数优化,这题别用蓝书上面的代码,一直卡常,吸氧吸中毒了都没用。
代码:
#include<bits/stdc++.h> using namespace std; const int N=1e6+5; int n; int trie[N][26],end[N],fail[N],tot; queue<int> q; void ins(char *str){ int len=strlen(str),p=0; for(int i=0;i<len;i++){ int ch=str[i]-'a'; if(!trie[p][ch]) trie[p][ch]=++tot; p=trie[p][ch]; } end[p]++; } void build(){ for(int i=0;i<26;i++) if(trie[0][i]) fail[trie[0][i]]=0,q.push(trie[0][i]); while(!q.empty()){ int u=q.front();q.pop(); for(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]; } } } int query(char *str){ int len=strlen(str),p=0,res=0; for(int i=0;i<len;i++){ p=trie[p][str[i]-'a']; for(int t=p;t&&end[t]!=-1;t=fail[t]) res+=end[t],end[t]=-1; } return res; } char tmp[N]; int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>tmp,ins(tmp); build(); cin>>tmp; printf("%d",query(tmp)); return 0; }
扩展看毛片。
其实我觉得有点像马拉车思想和KMP的结合,但这三个算法都是利用减少冗余重复计算来达到线性的。
相较于KMP算法,exKMP算法求的是模式串与文本串的后缀的LCP(最长公共前缀)
我们令 extend
数组为文本串 \(S\) 的后缀与模式串 \(T\) 的LCP,z
数组为模式串 \(T\) 的后缀与模式串 \(T\) 的LCP。
怎么来求呢?先画图。
我们假设当前已经求出了 \(1 \sim i\) 的 extend
数组和 z
数组,在匹配过程中记最远的匹配距离为 \(r\),即 \(r=max(i+extend[i]-1)\),能够取到最大值 \(r\) 的 \(i\) 我们记为 \(l\)。
z[i-l+1]
代表着 \(T[i-l+2\sim m]\) 中与 \(T[1 \sim m]\) 的最长公共前缀,我们设为 \(L\)。
所以 \(T[1\sim L]=T[i-l+2\sim i-l+2+L]\),图中蓝色与绿色部分长度字符都相等(下文简称“相等”)。
根据 \(l\) 和 \(r\) 的定义,可知 \(S[l\sim r]=T[1\sim r-l+1]\),所以 \(S[i+1\sim i+L]=T[i-l+2\sim i-l+2+L]\),图中红色与蓝色部分相等。
综上图中红绿蓝三个部分都相等
因为 \(S[i\sim n]\) 与 \(T[1\sim m]\) 的最长公共前缀为 extend[i]
,所以 extend[i]=L
。
我们令 extend[i]=r-i+1
靠暴力跑出剩下的答案。
那么从哪里开始跑暴力呢?
就从当前的 \(i\) 开始跑,与模式串一一比对。
最后别忘了更新一下 \(l\) 和 \(r\)。
对于 \(z\) 数组就是重复一遍这个算法的事情了。
因为每个点最多跑一次,所以做一遍的复杂度是线性的。
对 z
和 extend
分别做了一遍,所以总的时间复杂度为\(\Theta(n+m)\)。
代码:
#include<bits/stdc++.h> using namespace std; const int N=2e7+5; char s[N],t[N]; int lens,lent; int z[N],extend[N]; void doZ(){ z[1]=lent; for(int i=2,l=0,r=0;i<=lent;i++){ if(i<=r) z[i]=min(z[i-l+1],r-i+1); while(i+z[i]<=lent&&t[i+z[i]]==t[z[i]+1]) ++z[i]; if(i+z[i]-1>r) l=i,r=i+z[i]-1; } } void exkmp(){ doZ(); for(int i=1,l=0,r=0;i<=lens;i++){ if(i<=r) extend[i]=min(z[i-l+1],r-i+1); while(i+extend[i]<=lens&&s[i+extend[i]]==t[extend[i]+1]) ++extend[i]; if(i+extend[i]-1>r) l=i,r=i+extend[i]-1; } } int main(){ scanf("%s%s",s+1,t+1); lens=strlen(s+1);lent=strlen(t+1); exkmp(); long long ans1=0,ans2=0; for(int i=1;i<=lent;i++) ans1^=1ll*i*(z[i]+1); for(int i=1;i<=lens;i++) ans2^=1ll*i*(extend[i]+1); printf("%lld\n%lld",ans1,ans2); return 0; }
还有一点就是为什么跑暴力不分情况,写在循环外面,因为对于上述的情况一,不可能有 \(T[L+1]=S[i+L+1]\) 了。因为如果存在 \(T[L+1]=S[i+L+1]\),他们的最长公共前缀就是 \(L+1\) 了,\(L\) 就不是最长公共前缀了,就不满足 \(L\) 的定义了。所以只会在情况二的时候跑暴力,这也是算法的巧妙精简美啊!