KMP算法

KMP.java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class KMP {
    public static void main(String[] args) {
        //Scanner sc = new Scanner(System.in);
        //String str1 = sc.nextLine();//主串
        String str1 = "ababbabababbbab";//主串
        //while (sc.hasNext()) {
        //    String str2 = sc.nextLine();//模式串
            String str2 = "abababbbab";//模式串
            int next[] = new int[str2.length()];
            getNext(next, str2);//求解next数组
            System.out.println("next数组" + java.util.Arrays.toString(next));
            List<Integer> pos = new ArrayList<Integer>();//可能存在多个位置起始的字符串与模式串匹配，记录这些在主串中的位置
            ifMatch(str1, str2, next, pos);//字符串匹配过程
            System.out.println("匹配位置：" + pos);//输出所有匹配的位置
        //}
    }

    private static void ifMatch(String str1, String str2, int[] next, List<Integer> pos) {
        int j = 0;//主串初始位置
        int s = 0;//匹配串初始位置
        while (j < str1.length()) {
            if (s == -1 || str1.charAt(j) == str2.charAt(s)) {//比较字符是否相等
                j++;
                s++;
                if (s >= str2.length()) {//模式串被完全匹配
                    pos.add(j - str2.length());
                    s = 0;
                    j--;
                }
            } else {
                s = next[s];//不等，主串j不变，模式串s变
            }
        }
    }

    //next数组的求解
    private static void getNext(int[] next, String str) {
        next[0] = -1;
        int k = -1;
        int j = 0;
        while (j < str.length() - 1) {
            if(k >=0){
                System.out.println("k = " + k + "  char-k = " + str.charAt(k) + "   ,    j = " + j + "  char-j = " + str.charAt(j));
            } else {
                System.out.println("k = " + k + " char-k不取值  ,   j = " + j + "  char-j = " + str.charAt(j));
            }
            if (k == -1 || str.charAt(j) == str.charAt(k)) {//k==-1只为初始next数组的第二个元素为0
                j++;
                k++;
                System.out.println("j = " + j + "   ,   k = " + k);
                next[j] = k;
                System.out.println("next[" + j + "] = " + k + " ,,, next = " + printArr(next));
                System.out.println("\n");
            } else {
                System.out.println("k = " + k);
                System.out.println("next[" + k + "]====" + next[k]);
                k = next[k];//不相等k又变成-1，所以j指定位的next数组值为0（上面k++了）
                System.out.println("k = next[k] = " + k);
                System.out.println("next = " + printArr(next));
                System.out.println("\n");
            }
            //System.out.println("next = " + printArr(next));
        }
        //  0 1 2 3 4 5 6 7 8 9
        //  a b a b a b b b a b
    }

    private static String printArr(int[] arr){
        StringBuffer sb = new StringBuffer("[");
        for (int i : arr) {
            sb.append(i).append(" ,");
        }
        sb.deleteCharAt(sb.length() - 1);
        sb.append("]");
        return sb.toString();
    }
    /**
     * 你要求解当前位的next值，则看前一位与前一位next所在位字符是否相等，
     * 相等则当前位的next等于前一位next+1，如果不等就找前一位next的next与前一位比较，
     * 如果相等，当前位的next等于那个与前一位字符相等的字符所在位置+1，如果还是不相等，
     * 则以此类推，直到出现比较位为next[]=-1，那当前位的next就等于-1
     */
}