KMP算法

模拟过程

注意：p和s均从下标1开始存储

   i(初始位置为1)
s: ABABAABABACD
  j(初始位置为0)
p: ABABAC

==========================================================================

        i
s: ABABAABABACD
       j
p: ABABAC
因为s[i] != p[j+1], 所以j = next[j] = 1, j = 5时A的最长公共前后缀为1, 所以j移动到1

==========================================================================

        i
s: ABABAABABACD
       j
p:     ABABAC
因为s[i] != p[j+1], 所以j = next[j] = 0, j移动到0

===========================================================================

        i                          i
s: ABABAABABACD       s: ABABAABABACD
       j                           j
p:      ABABAC        p:      ABABAC
发现s[i] == p[j+1], 且一直到j-1 == n时, s[i] == p[j+1], 所以当j == n时, 匹配成功
匹配成功后, 后面可能还要可以匹配的子串, j = next[j]继续寻找

===========================================================================

              i
s: ABABAABABACD
             j
p:            ABABAC
因为s[i] != p[j+1], i已经走到s串结尾, 循环结束

Java代码

import java.io.*;
public class Main{
    private static int[] next;
    private static char[] p,s;
    private static int m,n;
    private static final int N = 10010;
    private static final int M = 100010;
    //求next数组
    static void next(){
        for (int i = 2, j = 0; i <= n; i ++ ){
            while (j != 0 && p[i] != p[j + 1]) j = next[j];
            if (p[i] == p[j + 1]) j ++ ;
            next[i] = j;
        }
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        next = new int[N];
        n = Integer.parseInt(br.readLine());
        String s1 = br.readLine();
        p = new char[N];
        for(int i = 1; i <= n; i++) p[i] = s1.charAt(i-1);
        m = Integer.parseInt(br.readLine());
        String s2 = br.readLine();
        s = new char[M];
        for(int i = 1; i <= m; i++) s[i] = s2.charAt(i-1);
        next();
        //匹配
        for(int i = 1, j = 0; i <= m; i++){
            while(j != 0 && s[i] != p[j+1]) j = next[j];
            if(s[i] == p[j+1]) j++;
            if(j == n){
                System.out.print(i-n+" ");
                j = next[j];
            }
        }
    }
}