题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1686

题意

查询字符串 $p$ 在字符串 $s$ 中出现了多少次，可重叠。

题解

KMP模板题。

Tips

需要关闭流同步，否则会超时。

代码

#include
using namespace std;
const int N = 1e6 + 100;

int Next[N];
string s, p;

void init_Next() {
Next[0] =Next[1] = 0;
for (int i = 1; i < p.size(); i++) {
int j = Next[i];
while (j and p[i] != p[j]) j = Next[j];
Next[i + 1] = (p[i] == p[j] ? j + 1 : 0);
}
}

void KMP() {
int ans = 0;
int j = 0;
for (int i = 0; i < s.size(); i++) {
while (j and s[i] != p[j]) j = Next[j];
if (s[i] == p[j]) j++;
if (j == p.size())
++ans;
}
cout << ans << "\n";
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int t; cin >> t;
while (t--) {
cin >> p >> s;
init_Next(), KMP();
}
}