KMP
相关
单个字符串匹配算法, 对模式串预处理求出 next 数组, 匹配时是模式串根据 next 数组进行跳转.
KMP 可用于匹配子串出现的位置, 次数.
更常见的应用是根据 next 数组的性质, 结合一些思维或者 dp.
\(next[i]\)即表示模式串前 \(i\)个字符的最长前缀后缀相等的长度.
也表示该最长相等后缀对应的前缀的末位置, i=next[i]就是表示跳到该前缀, 常用.
i-nex[i]则表示前缀 [0...i] 的循环节大小 (若有),i/(i-nex[i]) 就是表示循环节个数.
题目
CF471D MUH and Cube Walls
题意
有一面小墙和一面大墙, 小墙可上升下降, 问在大墙中能匹配多少个.
分析
很裸的可重叠 KMP 匹配子串个数, 因为墙可升可降, 即模式串可同加同减, 显然不变的是差分数组, 对差分数组进行 kmp 匹配即可, 注意特判模式串长度为 1 的情况.
代码
- #include <bits/stdc++.h>
- using namespace std;
- const int N=2e5+50;
- int a[N],b[N],n,m;
- int nex[N];
- void init(int s[],int n){
- int i=0,j=-1;
- nex[0]=-1;
- while(i<n){
- if(j==-1 || s[i]==s[j]){
- nex[++i]=++j;
- }else{
- j=nex[j];
- }
- }
- }
- int kmp(int s[],int n,int p[],int m){
- int i=0,j=0;
- init(p,m);
- int cnt=0;
- while(i<n && j<m){
- if(j==-1 || s[i]==p[j]){
- i++;
- j++;
- }else{
- j=nex[j];
- }
- if(j==m){
- cnt++;
- j=nex[j];
- }
- }
- return cnt;
- }
- int main(void){
- scanf("%d%d",&n,&m);
- for(int i=0;i<n;i++){
- scanf("%d",&a[i]);
- }
- for(int i=0;i<n-1;i++){
- a[i]=a[i+1]-a[i];
- }
- for(int i=0;i<m;i++){
- scanf("%d",&b[i]);
- }
- for(int i=0;i<m-1;i++){
- b[i]=b[i+1]-b[i];
- }
- int ans=kmp(a,n-1,b,m-1);
- if(m==1){
- // 注意特判
- ans=n;
- }
- printf("%d\n",ans);
- return 0;
- }
- hdu3336 Count the string
题意
近十年前的一道经典题, 给定字符串, 求所有前缀作为子串出现的次数之和.
分析
根据 next 数组的性质, 我们从后往前枚举前缀, 显然当 \(s[0...i-1]\)出现一次时,\(s[0...nex[i]-1]\)也出现了一次, 因此定义 dp 状态为 \(dp[i]\)表示长度为 i 的前缀出现的次数, 显然转移式为 \(dp[i]+=1\), 且 \(dp[nex[i]]+=dp[i]\).
代码
- #include <bits/stdc++.h>
- using namespace std;
- const int N=2e5+50;
- const int mod=10007;
- int T,n;
- char s[N];
- int nex[N];
- int dp[N];
- void init(char *s,int n){
- int i=0,j=-1;
- nex[0]=-1;
- while(i<n){
- if(j==-1 || s[i]==s[j]){
- nex[++i]=++j;
- }else{
- j=nex[j];
- }
- }
- }
- void solve(int n){
- for(int i=n;i>=1;i--){
- dp[i]++;
- dp[i]%=mod;
- dp[nex[i]]+=dp[i];
- dp[nex[i]]%=mod;
- }
- }
- int main(void){
- // freopen("in.txt","r",stdin);
- scanf("%d",&T);
- while(T--){
- memset(dp,0,sizeof(dp));
- scanf("%d",&n);
- scanf("%s",s);
- init(s,n);
- solve(n);
- int ans=0;
- for(int i=1;i<=n;i++){
- ans=(ans+dp[i])%mod;
- }
- printf("%d\n",ans);
- }
- return 0;
- }
来源: https://www.cnblogs.com/zxcoder/p/11261403.html