AcWing 831. 下标从0开始的写法
原题链接
简单
作者:
suncloud
,
2019-11-20 14:12:01
,
所有人可见
,
阅读 913
#include <bits/stdc++.h>
using namespace std;
const int M = 1e4 + 10;
const int N = 1e5 + 10;
char w[M], s[N];
int m, n
int f[M] = {-1, 0}; // 初始化失配表
// f[j]表示:s[i]跟w[j]不匹配时应该从前面第几个重新开始对比
// 注意:f的长度为m+1
void build_table() {
for (int i = 1; i < n; ++i) {
// f[i] is known, compute f[i + 1]
int j = f[i];
while (j && w[j] != w[i]) j = f[j];
if (w[j] == w[i]) f[i + 1] = j + 1;
}
}
void search() {
int j = 0;
for (int i = 0; i < n; ++i) {
while (j && w[j] != s[i]) j = f[j];
if (w[j] == s[i]) ++j;
if (j == m) {
cout << i - m + 1 << " ";
j = f[j];
}
}
}
int main() {
cin >> m >> w >> n >> s;
build_table();
search();
return 0;
}