kmp算法讲解
当我们在进行两个字符串判断时，我们最坏的打算的时间复杂度是n*m
这将会导致我们的时间是与给定的字符串挂钩的
那么，如何缩短判定时间呢
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)
next数组解释
什么是next数组，可以想象一下，当你在匹配时，以 i 为起点，匹配了 j-1个字符，但是第j个字符的时候，匹配的字符不相同，那该怎么办，这个匹配的字符串假设还有利用价值，也就是说，以i为起点，j为长度的字符串在后缀有存在于匹配字符串的子串时，是还有剩余价值的，这个时候，可以转到最大的前缀，这时候，当前的k应该为匹配的开头
如何实现nx数组
因为我们是匹配字符串，所以要在需要匹配的字符串种做操作，那么如何去做呢
因为我们现在在匹配过程中，如果出现当前位置字符不同的时候，只需要看当前位置我们能匹配长度为 l 的最大的前缀后缀的长度即可
//以下代码基于字符串从0开始c++版本 s2代表匹配字符串
for(int i=1,j=0;s2[i];i++)
{
//初始的时候，待匹配字符的下标应该是1，因为我匹配下标一直是从0开始(最大前缀)
while(j&&s2[i]!=s2[j])j=nx[j-1];//j代表当前匹配到的字符，如果说现在你的两个位置字符不能匹配，那么我就需要向之前位置的转移
if(s2[i]==s2[j])j++;//如果当前我能进行匹配，长度加一
nx[i]=j;//最后，顶下我当前位置的长度
}匹配过程
//以下代码基于字符串从0开始c++版本 s1代表待匹配字符串
for(int i=0,j=0;s1[i];i++)
{
//i代表s1现在为止的下标
//现在要对于你两个位置进行匹配，我待匹配字符串一定是不洞的，看我匹配字符串能否匹配
while(s1[i]!=s2[j]&&j)j=nx[j-1];
if(s1[i]==s2[j])j++;
//如果可以就break，这里看题目意思
if(j==s2.size())break;
}总体code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+7;
int nx[N];
int main()
{
string s1,s2;
cin>>s1>>s2;
for(int i=1,j=0;s2[i];i++)
{
while(j&&s2[i]!=s2[j])j=nx[j-1];
if(s2[i]==s2[j])j++;
nx[i]=j;
}
int ans=0;
for(int i=0,j=0;s1[i];i++)
{
while(s1[i]!=s2[j]&&j)j=nx[j-1];
if(s1[i]==s2[j])j++;
if(j==s2.size())
{
cout<<"yes";
return 0;
}
}
cout<<"no";
return 0;
}