AcWing 831. KMP字符串
标签：ble ios 匹配 next ++ 不能 print nbsp ext
https://www.acwing.com/problem/content/833/
#include using namespace std;
const int N = 10010, M = 100010;
int n, m;
int ne[N];
char s[M], p[N];
int main() {
cin >> n >> p + 1 >> m >> s + 1;
//求next过程
//i从2开始，因为next[1]=0,如果第一个字母失败了，只能从0开始
for (int i = 2, j = 0; i ) {
while (j && p[i] != p[j + 1])
j = ne[j];
if (p[i] == p[j + 1])
j ++ ;
ne[i] = j;
}
//kmp匹配过程
for (int i = 1, j = 0; i ) {
while (j && s[i] != p[j + 1]) //当j没有退回起点，并且当前的s[i]不能和下一个j的位置匹配
j = ne[j];//移动，保证之前的相等 直到匹配位置，或者j已经到开头了
if (s[i] == p[j + 1]) //如果已经匹配了
j ++ ; //j往下移动
if (j == n) {//说明匹配成果
printf("%d ", i - n+1);
j = ne[j];
}
}
return 0;
}
AcWing 831. KMP字符串
标签：ble ios 匹配 next ++ 不能 print nbsp ext
原文地址：https://www.cnblogs.com/QingyuYYYYY/p/11790107.html
评论