本文共 916 字，大约阅读时间需要 3 分钟。
求模式串在待匹配串的出现次数。
kmp
#include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const int MAXN = 1e6 + 10;const int MAXM = 1e4 + 10;int Next[MAXM];string a, b;void Get_Next(int m){ int k = -1; int j = 0; Next[j] = k; while (j < m) { if (k == -1 || b[j] == b[k]) { j++; k++; Next[j] = k; } else k = Next[k]; }}int Kmp(int n, int m){ int i = 0; int j = 0; int res = 0; Get_Next(m); while (i < n) { if (j == -1 || a[i] == b[j]) i++, j++; else j = Next[j]; if (j == m) res++; } return res;}int main(){ int t, n, m; cin >> t; while (t--) { memset(Next, 0, sizeof(Next)); cin >> b >> a; cout << Kmp(a.length(), b.length()) << endl; } return 0;}
转载于:https://www.cnblogs.com/YDDDD/p/10552649.html