浙大数据结构：KMP 字符串匹配算法比较
主要是学习Kmp匹配算法
如果不会可以到下面这个链接学一下
Kmp算法学习
Kmp算法
先是构造前缀数组，然后进行匹配
#include <iostream>
#include<string>
using namespace std;
#define endl '\n'
int kmp(string s,string t)
{
int j=-1;
int next[100005];
next[0]=j;
for(int i=1;i<t.size();i++)
{
while(j>=0&&t[i]!=t[j+1])j=next[j];
if(t[i]==t[j+1])j++;
next[i]=j;
// cout<<i<<' '<<j<<' '<<next[i]<<endl;
}
// cout<<endl;
j=-1;
for(int i=0;i<s.size();i++)
{
while(j>=0&&s[i]!=t[j+1])j=next[j];
if(s[i]==t[j+1])j++;
if(j==(t.size()-1))return i-t.size()+1;
//cout<<j;
}
return -1;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string str;
cin>>str;
int n;
cin>>n;
while(n--)
{
string s;
cin>>s;
int k=kmp(str,s);
if(k>=0)cout<<str.substr(k);
else cout<<"Not Found";
cout<<endl;
}
return 0;
}