KMP
字符串最重要的算法我认为是KMP,为了方便复习写一下重点:
ne[i]代表前缀i的最长 前缀==后缀 的长度。
求ne数组:
for(int i=2,j=0;i<=n;i++){
while(j&&p[i]!=p[j+1]) j=ne[j];//失配直接跳
if(p[i]==p[j+1]) j++;//配上了直接下一位
ne[i]=j;//记录一下
}
感觉理解了一遍kmp之后就很清晰了
要点:
- 不要弄混字符串p和s
- 扩展ne数组不要想复杂
后面一开始的题是KMP的扩展,比较重要
AC自动机
相当于是字典树版本的KMP,可以在树上建出多个字符串的ne数组。
注意 AC自动机-> Trie图的优化,代码更简单还高效。
还没怎么做AC自动机的题呢。。。现在学了这个只是花架子,这两三天必须复习+做题【待填坑】
Problems:
P2375 [NOI2014] 动物园
求出数组num,为最长的相等且不重合的前后缀的数量(ne数组加上限制)
可以发现 ne[i] , ne[ne[i]] ,ne[ne[ne[i]]] 之类的都为 前后缀相等的可能长度。考虑直接暴力跳ne,可是会超时。
于是先预处理出num数组,但这里的num[i]预处理的是读入的字符串的前缀i,不停跳ne直到为0的次数。初始化ans[1]=1
Δ P3426 [POI2005] SZA-Template
思路Luogu第一篇题解/bx ,但是自认为注释比这位大佬写得好
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
int n,ne[N],f[N],h[N];char s[N];
signed main(){
scanf("%s",s+1);n=strlen(s+1);
for(int i=2,j=0;i<=n;i++){
while(j&&s[i]!=s[j+1]) j=ne[j];
if(s[i]==s[j+1]) j++;
ne[i]=j;
}
for(int i=1;i<=n;i++){//一定从1开始
f[i]=i;
if(h[f[ne[i]]]>=i-ne[i]) f[i]=f[ne[i]];
h[f[i]]=i;
}
printf("%d",f[n]);
return 0;
}
/*
设f(i)为前缀i的答案
考虑f(i)只有两种取值,即f(i)和f(ne[i])
因为如果覆盖i至少覆盖前缀 ,否则前缀可以更大则矛盾
f(i)的转移:若f(j)可行并且 j>=i-ne[i],f(i)=f(ne[i])
因为此时前缀j是可以被覆盖的,故再拼接上一个ne[i]就行,所以ne[i]可以覆盖前缀i
于是我们考虑能否有东西还能覆盖前缀ne[i],所以f[i]=f[ne[i]]
还有前提:ne[i]必须等于ne[j],因为是用一个相同的字符串覆盖前缀
j越大越可能满足 j>=i-ne[i] 的条件,所以开桶h[x]表示前缀为x的时候
最大的j,如果满足如上条件,则进行转移即可
*/
P4824 [USACO15FEB] Censoring S
非常巧妙的扩展。发现其实每一遍删除就是匹配操作,所以预处理ne后进行匹配。
但是考虑删掉一个后可能前面与后面的能拼起来,所以用一个栈来储存每个i对应的j,之后每次j==m(匹配上了)就从栈中删去m个,然后让j赋值为从此时的栈顶,继续跑匹配就行。
太妙了!!
P3435 [POI2006] OKR-Periods of Words
题面:对于字符串a,求一个a的真前缀p,且a为p+p的前缀,则称p为a的最大真周期。求给定字符串str的每个前缀的最大真周期之和。
考虑”求一个a的真前缀p,且a为p+p的前缀”意味着什么,其实就是求a的最小前缀=后缀的长度,且不能为0。则答案为|a|-L
可以想到另一个点:最后的a的最小前缀=后缀一定能不断跳next得到(KMP经典结论)
所以直接开跳!加上记忆化