KMP

KMP

什么是KMP算法，这是一个字符串匹配算法，对暴力的匹配方法进行了优化，使时间复杂度大大降低

然后是一些基本概念：

1、s[ ]是模式串，即比较长的字符串。
2、p[ ]是模板串，即比较短的字符串。

KMP主要分两步：求next数组、匹配字符串。

模版：

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

模板串 PP 在模式串 SS 中多次作为子串出现。

求出模板串 PP 在模式串 SS 中所有出现的位置的起始下标。

输入格式

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

第二行输入字符串 PP。

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

第四行输入字符串 SS。

输出格式

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

数据范围

1≤N≤1051≤N≤105
1≤M≤1061≤M≤106

输入样例：

3
aba
5
ababa

输出样例：

0 2

import java.util.*;
import java.io.*;

public class Main {
    
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(reader.readLine());
        char[] p = reader.readLine().toCharArray();
        int m = Integer.parseInt(reader.readLine());
        char[] s = reader.readLine().toCharArray();
        // next数组
        int[] next = new int[n];
        for(int i = 1, j = 0; i < n; ++i) {
            while(j > 0 && p[i] != p[j])
                j = next[j - 1];
            if(p[i] == p[j])
                j++;
            next[i] = j;
        }
        // 匹配
        for(int i = 0, j = 0; i < m; ++i) {
            while(j != 0 && s[i] != p[j])
                j = next[j - 1];
            if(s[i] == p[j])
                j++;
            if(j == n) {
                writer.write(i - n + 1 + " ");
                j = next[j - 1];
            }
        }
        writer.flush();
    }
}