AcWing 831. KMP字符串

KMP 字符串

#include <iostream>

using namespace std;

const int N = 1e6 + 10;
int n, m;
char p[N], s[N];
int ne[N];

int main(){
    cin >> n >> p + 1 >> m >> s + 1;
    for(int i = 2, j = 0; i <= n; i++){
        while(j && p[i] != p[j + 1]) j = ne[j];
        if(p[i] == p[j + 1]) j++;
        ne[i] = j;
        //这里是匹配成功然后把最长公共前缀和后缀的最后一位的下标加next数组里
    }
    for(int i = 1, j = 0; i <= m; i++){
	    while(j && s[i] != p[j + 1]) j = ne[j];
	    if(s[i] == p[j + 1]) j++;
	    if(j == n){
		    printf("%d ", i - n);
		    j = ne[j];
	    }
    }
    return 0;
}

# 不断重复 j = ne [j] , j 最终会变为 0，这应该就是退无可退了吧，这个 while 循环会当 j == 0 时 break 掉

#include <iostream>

using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;

int n, m;
char p[N], s[M];
int ne[N];

int main(){
    cin >> n >> p + 1 >> m >> s + 1;
    //因为下标从1开始 所以p + 1 s + 1
    
    //求next数组过程
    for(int i = 2, j = 0; i <= n; i++){
        while(j && p[i] != p[j + 1]) j = ne[j];
        if(p[i] == p[j + 1]) j++;
        ne[i] = j;
    }
    
    //匹配过程
    //枚举过程 当前一位是s[i] 但是p的话是p[j + 1] 所以p是往前错一位
    for(int i = 1, j = 0; i <= m; i++){
        while(j && s[i] != p[j + 1]) j = ne[j];
        //while循环结束 有两种条件 第一种是j退无可退 第二种的话是已经匹配了
        if(s[i] == p[j + 1]) j++;
        //因为是j + 1 所以p是往前错一位所以此时直接匹配
        if(j == n){
            //匹配成功
            printf("%d ", i - n);
            j = ne[j];
            //匹配成功了再往后退一步就可以继续做
        }
    }
    
    return 0;
}