## 【kmp】AcWing160

### 传送门

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 233;
int n, m, q;
char a[maxn], b[maxn];
int ne[maxn], f[maxn];
int main()
{
cin >> n >> m >> q;
cin >> a + 1 >> b + 1;
ne[1] = 0;
for(int i =2, j = 0; i <= m; i++)
{
while(j > 0 && b[i] != b[j + 1]) j = ne[j];
if(b[i] == b[j + 1]) j++;
ne[i] = j;
}
for(int i = 1, j = 0; i <= n; i++)
{
while(j > 0 && (j == m || a[i] != b[j + 1])) j = ne[j];
if(a[i] == b[j + 1]) j++;
f[j]++;
}
for(int i = m; i; i--) f[ne[i]] += f[i];
for(int i = 1; i <= q; i++)
{
int k; scanf("%d", &k);
printf("%d\n", f[k] - f[k + 1]);
}
}



## 然而有无脑二分的做法。。。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 233;
typedef unsigned long long ull;
int n, m, q;
char a[maxn], b[maxn];
int f[maxn];
ull h1[maxn], h2[maxn], p[maxn], base = 131;
ull get(ull h[], int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}
bool gao(int x, int k)
{
return get(h2, 1, 1 + k) == get(h1, x, x + k);
}
int main()
{
cin >> n >> m >> q;
cin >> a + 1 >> b + 1;
p[0] = 1;
for(int i = 1; i <= max(n, m); i++) p[i] = p[i - 1] * base;
for(int i = 1; i <= n; i++) h1[i] = h1[i - 1] * base + a[i] - 'a' + 1;
for(int i = 1; i <= m; i++) h2[i] = h2[i - 1] * base + b[i] - 'a' + 1;
for(int i = 1; i <= n; i++)
{
int l = 0, r = min(n, m);
while(l < r)
{
int mid = (l + r) >> 1;
if(gao(i, mid)) l = mid + 1;
else r = mid;
}
f[l]++;
}
for(int i = 1; i <= q; i++)
{
int k; scanf("%d", &k);
printf("%d\n", f[k]);
}
}