当前位置：首页 > article >正文

Acwing831KMP字符串

article 2024/9/23 17:22:40

题目

给定一个字符串 S，以及一个模式串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模式串 P 在字符串 S 中多次作为子串出现。

求出模式串 P 在字符串 S 中所有出现的位置的起始下标。

输入格式

第一行输入整数 N，表示字符串 P 的长度。

第二行输入字符串 P

第三行输入整数 M，表示字符串 S 的长度。

第四行输入字符串 S

输出格式

共一行，输出所有出现位置的起始下标（下标从 00 开始计数），整数之间用空格隔开。

数据范围

1≤N≤10^5
1≤M≤10^6

输入样例：

3
aba
5
ababa

输出样例：

0 2

代码

import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String p = in.next();
        int m = in.nextInt();
        String s = in.next();
        // p = p + " ";
        // s = s + " ";
        int[] ne = new int[n + 1];

        // 预处理模式串
        for (int i = 2, j = 0; i <= n; i++) {
            while (j > 0 && p.charAt(i - 1) != p.charAt(j)) j = ne[j];
            if (p.charAt(i - 1) == p.charAt(j)) j++;
            ne[i] = j;
        }

        StringBuilder result = new StringBuilder();

        // 在目标串中搜索模式串
        for (int i = 1, j = 0; i <= m; i++) {
            while (j > 0 && s.charAt(i - 1) != p.charAt(j)) j = ne[j];
            if (s.charAt(i - 1) == p.charAt(j)) j++;
            if (j == n) {
                result.append(i - n).append(" ");  // 将匹配的位置添加到StringBuilder中，一次性输出，解决超时问题
                j = ne[j];
            }
        }
        System.out.print(result.toString());

    }
}