C++ KMP算法模板代码

KMP算法模板代码

#include // 头文件

#include

using namespace std; int pi[10005];

void prefix_function(string s) { int n=s.length();

for(int i=1;i

while(j>0&&s[j]!=s[i]) j=pi[j-1]; if(s[j]==s[i]) j++;

pi[i]=j;

// 以i结尾的字符串的前缀函数

} }

int kmp(string a,string b) // 核心代码 {

int n=a.length(),m=b.length(); int j=0,ans=0;

for(int i=0;i

while(j>0&&a[i]!=b[j]) j=pi[j-1]; if(a[i]==b[j]) j++; if(j==m) { ans++;

j=pi[j-1]; } }

return ans; }

int main() {

ios::sync_with_stdio(0); // 加速 string s1,s2; int t; cin>>t;

while(t--) { cin>>s1>>s2;

prefix_function(s1); cout<

}

return 0; }