13_KMP字符匹配算法

要求：{A,B,A,B,C,A,B,A,A}=> {'A','B','A','B','A','B','A','B','C','A','B','A','A','B'}，找出匹配的字符串在原始的第几位。
讲解推荐

思路:使用kmp字符匹配算法,kmp算法的核心思想是利用比对失败的信息,减少模式串与目标串的比对次数.
0、利用需要匹配的字符串，求出前缀表，计算prefix数组，采用动态规划
1、把计算出来的前缀表往后移动一格，最后一位不要，prefix[0]=-1
2、进行字符匹配

public class L13_KMLP{
    // 第一步，求前缀表
    public static int[] Prefix(char[] arr){
        int j = 0;
        int i = 1;
        int n = arr.length;
        // suffix(S): S的所有后缀的集合
        // prefix(S): S的所有前缀的集合
        // prefix[i]代表的意义是suffix(c[1]c[2]......c[i])与prefix(c[1]c[2]......c[i])两个集合中最长相同串的长度
        int[] prefix = new int[n];
        prefix[0] = 0;
        while(i<n){
            // 求第i行的前缀数
            if(arr[j] == arr[i]){
                // 遇到相等，加一
                prefix[i] = j+1;
                j++;
                i++;
            }else {
                if(j>0){
                    j = prefix[j-1];
                } else{
                    prefix[i] = j;
                    i++;
                }

            }
        }
        return prefix;
    }
    // 第二步，前缀表后移一位，并给prefix[0]赋-1；
    public static int[] Move_prefix(int[] arr){
        int[] newarr = new int[arr.length];
        for(int i = 1, j =0; i < arr.length; i++,j++){
            newarr[i] = arr[j];
        }
        newarr[0] = -1;
        return newarr;
    }

    // 进行字符匹配
    public static void kmp_search(char[] text, char[] pattern){
        int i = 0;  // text上的指针
        int j = 0;  // pattern上的指针

        int[] pf = Prefix(pattern);
        int[] prefix = Move_prefix(pf);
        int m = text.length;  // text的长度
        int n = pattern.length;  // pattern 的长度
        while(i<m){
            // text最后一位匹配成功
            if(j==n-1 && text[i] == pattern[j]){
                System.out.printf("Fount pattern at %d\n", i-j );
                j = prefix[j];
            }
            // 往后移动，匹配遇到不相等的将j指向prefix[j]位置
            if(text[i] == pattern[j]){
                i++;
                j++;
            }else{
                j = prefix[j];
                // 如果j指向了第一位
                if(j == -1){
                    i++;
                    j++;
                }
            }
        }

    }
    public static void main(String[] args) {
        char[] arr ={'A','B','A','B','A','B','A','B','C','A','B','A','A','B'};
        char[] pattern = {'A','B','A','B','C','A','B','A','A'};
        kmp_search(arr,pattern);
    }
}