算法题：KMP字符串匹配

问题描述

给出两个字符串 s1 和 s2，若 s1 的区间 [l,r] 子串与 s2 完全相同，则称 s2 在 s1 中出现了，其出现位置为 l。 现在请你求出 s2 在 s1 中所有出现的位置。

定义一个字符串 s 的 border 为 s 的一个非 s 本身的子串 t，满足 t 既是 s 的前缀，又是 s 的后缀。 对于 s2，你还需要求出对于其每个前缀 s' 的最长 border t' 的长度。

输入格式

第一行为一个字符串，即为 s1。 第二行为一个字符串，即为 s2。

输出格式

首先输出若干行，每行一个整数，按从小到大的顺序输出 s2 在 s1 中出现的位置。 最后一行输出 |s_2| 个整数，第 i 个整数表示 s2 的长度为 i 的前缀的最长 border 长度。

样例

输入

ABABABC
ABA

输出

1
3
0 0 1

数据范围

本题采用多测试点捆绑测试，共有 3 个子任务。

• Subtask 1（30 points）：∣s1∣≤15，∣s2∣≤5。
• Subtask 2（40 points）：∣s1∣≤10^4，∣s2∣≤10^2。
• Subtask 3（30 points）：无特殊约定。 对于全部的测试点，保证 1 ≤∣s1∣,∣s2∣≤10^6，s1,s2 中均只含大写英文字母。

解决方案

思路

代码

#include <iostream>

using namespace std;


void cal_next(const char *str, int *next, int len) {
    next[1] = 0;
    next[2] = 1;
    int i = 2;
    int j = 1;
    while (i < len) {
        if (j == 0 || str[i - 1] == str[j - 1]) {
            i++;
            j++;
            if (str[i - 1] != str[j - 1]) {
                next[i] = j;
            } else {
                next[i] = next[j];
            }
        } else {
            j = next[j];
        }
    }
}

int KMP(const char *str, const char *sub, int *next, int strLen, int subLen, int start = 1) {
    int i = start;
    int j = 1;
    while (i <= strLen && j <= subLen) {
        if (j == 0 || str[i - 1] == sub[j - 1]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j > subLen) {
        return i - subLen;
    }

    return -1;
}

int main() {

    string str, sub;
    cin >> str >> sub;


    static int next[1000005];
    cal_next(sub.c_str(), next, sub.length());

    int temp = 0;
    while (true) {
        temp = KMP(str.c_str(), sub.c_str(), next, str.length(), sub.length(), temp + 1);

        if (temp == -1)
            break;

        cout << temp << endl;
    }
    for (int i = 0; i < sub.size(); ++i) {
        cout << next[i] << " ";
    }
    return 0;
}