甘肃省省经合局网站建设的通知,专门做塑胶原料副牌网站,网站开发人员培训,百度提交收录入口KMP数组存的是什么
对于一个字符串 b,下标从1开始。
则kmp[i]表示 以i结尾的连续子串 s的前缀的最大值#xff08;等价于前缀最大结尾处#xff09;
如何求KMP
假设 i 以前的KMP都被求出来了。
j 表示上一个字符可以成功匹配的长度#xff08;等价于下标#xff09; …KMP数组存的是什么
对于一个字符串 b,下标从1开始。
则kmp[i]表示 以i结尾的连续子串 s的前缀的最大值等价于前缀最大结尾处
如何求KMP
假设 i 以前的KMP都被求出来了。
j 表示上一个字符可以成功匹配的长度等价于下标
如果b[j1] ! b[i]下一个位置匹配不上即不能成为前缀
则让j kmp[j] 即成为以j结尾的 连续子串 的 最长前缀 尾部的下标
退出循环后若还能匹配上则j(本质是加上i的贡献。因为j 0时可能匹配不上)
然后让kmp[i] j即可。
运用kmp
和求kmp差不多如果匹配不上求让a[i]和以j结尾的连续子串的最长前缀匹配。放宽要求
算法正确性证明
用哲学的话来说就是每一次失败都会让我变得更强大。
当匹配不上时匹配串b至少会前移1位由指针的思想。O(n)可证。
#includebits/stdc.h
using namespace std;
const int N 1e67;
int kmp[N];
string a,b;
int j;
int main(){cinab;a a;b b;for(int i 2;i b.size();i){while(jb[j1] ! b[i]){j kmp[j];}if(b[j1] b[i])j;kmp[i] j;}j 0;for(int i 1;i a.size();i){while(ja[i] ! b[j1]){j kmp[j];}if(b[j1] a[i])j;if(j b.size()-1){couti-(b.size()-1)1endl;jkmp[j];}}for (int i1;i b.size();i)coutkmp[i] ;return 0;
}
