洛谷P3375 【模板】KMP

P3375 【模板】KMP

这题有很多多少讲法，我的不肯定清晰，只管讲吧
什么是KMP算法？

所谓的KMP，就是在主串中快速地找出模式串的位置
这里我们必要一个fail数组，此中fail的意思是模式串前i个字符的前缀的最长公共前后缀
接下来我会拿图来表明：

此时开始遍历每一个字符，直到......

下一个字符不匹配！！！！！
那咋办？
如果重新开始重新遍历，时间复杂度将会大爆炸......
那有没有更快的方法？有的，就是KMP：
由于fail数组存的是模式串的前i个字符构成的前缀的最长公共前后缀，
那么拿此图来讲，模式串中字符d的前面肯定是跟主串一样，

那么显然的，赤色部门与黄色部门是完全相当的，此时我们就可以偷懒了，
将指针j调到fail[j]继承匹配。
为什么跳到fail[j]？

fail[j]表现的是最长公共前后缀，就是赤色部门的长度！！
以是我们的指针跳到fail[j]，

注：也可以明确为讲模式串的第fail[j]位跳到j的位置:

那么不停遍历到竣事......

发现全部都符合，于是我们找到了答案。
标题剖析

此标题中的border就是fail数组的每个值（不表明）
以是我们在举行查找过后，直接输出fail数组的值就好了
其他的依照上述的KMP解说写就好了
绝对不是我懒得写剖析
ACcode:

[code]//实在剖析在这里(doge)#includeusing namespace std;const int N=1e6+5;int f[N];//f：模式串t的前i-1个字符的最长雷同前后缀长度int main(){        ios::sync_with_stdio(false);        cin.tie(0);        string s,t;        cin>>s>>t;        for(int i=2;i