Luogu P3805 manacher算法
马拉车算法是求最长回文串的算法,其核心在于减少了冗余的重复计算,利用当前已知的数据尽可能的推出之后的数据,从而达到线性的复杂度。
我认为这个算法的核心之处是充分利用了回文串的对称性。
首先是处理回文串的一个小技巧,对于奇偶回文串,我们只需要在相邻的两个字符之间加上一个 '#' 字符,那么无论是奇串还是偶串,都会变成奇串(自行模拟)。
对于你目前已经求出的回文串 \([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;
}
Luogu P1368 最小表示法
最小表示法就是对于一个字符串,求她的循环同构的字符串的最小的那个。
如字符串 "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;
}
Luogu P3375 KMP字符串匹配
激动人心的 看毛片 算法来了
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;
}
Luogu P3808 AC自动机(简单版)
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;
}
Luogu P5410 扩展KMP(Z函数)
扩展看毛片。
其实我觉得有点像马拉车思想和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\)。
- 第一种情况,当 \(i+L\) 在 \(r\) 左边时:
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
。
- 第二种情况,当 \(i+L\) 在 \(r\) 右边时:
我们令 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\) 的定义了。所以只会在情况二的时候跑暴力,这也是算法的巧妙精简美啊!