KMP 字符串匹配问题

一 原问题链接

【模板】KMP字符串匹配 - 洛谷https://www.luogu.com.cn/problem/P3375

二 输入和输出

1 输入

第 1 行为字符串 s1，第 2 行为字符串 s2。字符串只含大写英文字母。

2 输出

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

三 输入和输出样例

1 输入样例

ABABABC

ABA

2 输出样例

1

3

0 0 1

四 分析

本问题实质上是模式匹配和求解 KMP 算法中 next[] 数组的问题。

五 算法设计

1 输入字符串 s 和 t，采用 KMP 算法从头开始查找 t 在 s 中出现的位置。

2 求解字符串 t 的 next[] 数组。next[i] 表示 t 的长度为 i 的前缀的最长 border 的长度。

六 代码

package p3375;

import java.util.Scanner;

public class P3375 {
    static int slen;
    static int tlen;
    static int next[] = new int[1000000 + 5];

    // 求模式串 T 的 next 函数值
    static void get_next(String t) {
        int j = 0, k = -1;
        next[0] = -1;
        while (j < tlen) {//模式串t的长度
            if (k == -1 || t.charAt(j) == t.charAt(k))
                next[++j] = ++k;
            else
                k = next[k];
        }
    }

    static void KMP(String s, String t) {
        int i = 0, j = 0;
        slen = s.length();
        tlen = t.length();
        get_next(t);
        while (i < slen) {
            if (j == -1 || s.charAt(i) == t.charAt(j)) { // 如果相等，则继续比较后面的字符
                i++;
                j++;
            } else
                j = next[j]; // j 回退到 next[j]
            if (j == tlen) { // 匹配成功
                System.out.println(i - tlen + 1);
                j = next[j]; // 不允许重叠，j从0重新开始，如果允许重叠，j=nex[j]
            }
        }
    }

    public static void main(String[] args) {
        String s, t;
        Scanner scanner = new Scanner(System.in);
        s = scanner.nextLine();
        t = scanner.nextLine();
        KMP(s, t);
        for (int i = 1; i <= tlen; i++)
            System.out.print(next[i] + " ");
    }
}

七 测试

绿色为输出，白色为输出。