本文主要是介绍【KMP】【模板】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/*
pku3461(Oulipo), hdu1711(Number Sequence)
这个模板 字符串是从0开始的
Next数组是从1开始的*/
#include <iostream>
#include <cstring>
using namespace std;const int N = 1000002;
int next[N];
char S[N], T[N];
int slen, tlen;void getNext()
{int j, k;j = 0; k = -1; next[0] = -1;while(j < tlen)if(k == -1 || T[j] == T[k])next[++j] = ++k;elsek = next[k];}
/*
返回模式串T在主串S中首次出现的位置
返回的位置是从0开始的。
*/
int KMP_Index()
{int i = 0, j = 0;getNext();while(i < slen && j < tlen){if(j == -1 || S[i] == T[j]){i++; j++;}elsej = next[j];}if(j == tlen)return i - tlen;elsereturn -1;
}
/*
返回模式串在主串S中出现的次数
*/
int KMP_Count()
{int ans = 0;int i, j = 0;if(slen == 1 && tlen == 1){if(S[0] == T[0])return 1;elsereturn 0;}getNext();for(i = 0; i < slen; i++){while(j > 0 && S[i] != T[j])j = next[j];if(S[i] == T[j])j++;if(j == tlen){ans++;j = next[j];}}return ans;
}
int main()
{int TT;int i, cc;cin>>TT;while(TT--){cin>>S>>T;slen = strlen(S);tlen = strlen(T);cout<<"模式串T在主串S中首次出现的位置是: "<<KMP_Index()<<endl;cout<<"模式串T在主串S中出现的次数为: "<<KMP_Count()<<endl;}return 0;
}
/*
test case
4
aaaaaa a
abcd d
aabaa b
*/这篇关于【KMP】【模板】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
