Today is a very difficult and messy algorithm—KMP, used to deal with the String matching problem.
给定一个模式串S，以及一个模板串P，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模板串P在模式串S中多次作为子串出现。
求出模板串P在模式串S中所有出现的位置的起始下标。
输入格式 第一行输入整数N，表示字符串P的长度。
第二行输入字符串P。
第三行输入整数M，表示字符串S的长度。
第四行输入字符串M。
输出格式 共一行，输出所有出现位置的起始下标（下标从0开始计数），整数之间用空格隔开。
数据范围 1≤N≤104 1≤M≤105 输入样例： 3 aba 5 ababa 输出样例： 0 2
KMP need an array to describe the prefix and suffix number. Very difficult to prove in math. Give the module of KMP:
import java.io.*; public class Main{ static PrintWriter pw = new PrintWriter(System.out); static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static int n, m; static char longer[], shorter[]; static int next[]; public static void main(String []args) throws IOException { n = Integer.parseInt(br.readLine()); String input1 = br.readLine(); m = Integer.parseInt(br.readLine()); String input2 = br.readLine(); longer = new char[m + 2]; shorter = new char[m + 2]; next = new int[n + 2]; for (int i = 1; i <= m; i++) longer[i] = input2.charAt(i - 1); for (int i = 1; i <= n; i++) shorter[i] = input1.charAt(i - 1); //next for (int i = 2, j =0; i <= n; i++ ) { while (j != 0 && shorter[i] != shorter[j + 1]) j = next[j]; if (shorter[i] == shorter[j + 1]) j++; next[i] = j; } for (int i = 1, j = 0; i <= m; i++ ) { while (j != 0 && longer[i] != shorter[j + 1]) j = next[j]; if (longer[i] == shorter[j + 1]) j++; if (j == n) { pw.print(i - n + " "); j = next[j]; } } pw.flush(); } }