深入理解KMP算法

作者: pianpianboy | 来源:发表于2018-03-13 11:08 被阅读0次

深入理解KMP算法
对KMP算法的一些理解
KMP算法学习札记
KMP算法理解与实现
理解字符串匹配KMP算法的一些细节
KMP算法
数据结构与算法14-字符串匹配与KMP
字符串匹配问题-KMP算法
KMP 专题整理
理解 KMP 算法

深入理解KMP算法

时间：20180313

KMP算法的核心是求公共最大前后缀。

public class Prefix {
    //求前缀后缀的最长子串
    public static int [] getPrefix(char patern[]){
        int [] prefix = new int [patern.length];
        //第一个前后缀最长子缀为0
        prefix[0] = 0;
        int i = 1;
        while(i < patern.length){
            //System.out.println("i: "+ i +" prefix[i] : "+ prefix[i]);
            //正常情况下：当前值(第i个值)等于前面一串的字符串已知prefix[i-1]的情况下去判断
            //当前值patern[i]与patern[prefix[i-1]]的大小，若相等则在patern[prefix[i-1]]基础上加1
            //若不相等继续进行判断，判断逻辑见画图分析
            if(patern[i] == patern[prefix[i-1]]){
                prefix[i] = prefix[i-1] + 1;
                i++;
            }else{
                //处理当前值patern[i]与patern[prefix[i-1]]不相等的情况
                if(prefix[i-1] > 0){
                    //取得右偏一位后值的最大公共前后缀
                    prefix[i] = prefix[prefix[i-1]-1];
                    i++;
                }else{
                    prefix[i] = 0;
                    //防止死循环
                    i++;
                }
            }
        }
        return prefix;
    }
    
    //将prefix数组中的值逐步向后移动一位
    public static int[] movePrefix(int[] prefix){
        for(int i= prefix.length-1; i > 0; i--){
            prefix[i] = prefix[i-1];
        }
        prefix[0] = -1;
        return prefix;
    }

    public static void main(String[] args) {
        String s = "ABABCABAA";
        System.out.println(s);
        char [] patern = s.toCharArray();
        int [] res = getPrefix(patern);
        res = movePrefix(res);
        for(int i = 0; i < res.length; i++){
            System.out.println(res[i]);
        }
    }
}