浙大数据结构：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;
}