搞了一晚上终于理解了算法原理并且理清了代码逻辑,之前了解过KMP,原理还好理解,只不过动手实现的时候反而无从下手OωO

题目链接

洛谷P3375

题目分析

  • 首先对模式串预处理,nxt数组代表每个位置对应的前后缀匹配的最长长度
  • 两个字符串匹配的时候和预处理时差不多
  • strlen时间复杂度为O(n), 注意输入完字符串后直接用变量代替,直接在过程中用这个函数会T

题目代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int nxt[N], len1, len2;
char s1[N], s2[N];

void init() {
    nxt[0] = -1;
    int i = 0, j = -1;
    while (i < len2) {
        if (j == -1 || s2[i] == s2[j]) {
            ++i;
            ++j;
            nxt[i] = j;
        } else 
            j = nxt[j];
    } 
}

void kmp() {
    int i = 0, j = 0;
    while (i < len1) {
        if (j == -1 || s1[i] == s2[j]) {
            ++i;
            ++j;
        } else {
            j = nxt[j];
        } 
        if (j == len2) {
            printf("%d\n", i - len2 + 1);
            j = nxt[j];
        } 
    }
}

int main() {
#ifndef ONLINE_JUDGE    
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    scanf("%s", s1);
    scanf("%s", s2);
    len1 = strlen(s1), len2 = strlen(s2);
    init();
    kmp();
    for (int i = 1; i <= len2; i++) 
        printf("%d ", nxt[i]);
        
    return 0;
}
最后修改:2021 年 04 月 02 日 10 : 01 PM