KMP算法

KMP算法

一个人能能走的多远不在于他在顺境时能走的多快，而在于他在逆境时多久能找到曾经的自己

————KMP

参考代码：

public class KMP {
    public static int kmp(String str, String dest,int[] next){//str文本串  dest 模式串
        for(int i = 0, j = 0; i < str.length(); i++){
            while(j > 0 && str.charAt(i) != dest.charAt(j)){
                j = next[j - 1];
            }
            if(str.charAt(i) == dest.charAt(j)){
                j++;
            }
            if(j == dest.length()){
                return i-j+1;
            }
        }
        return 0;
    }
    public static int[] kmpnext(String dest){
        int[] next = new int[dest.length()];
        next[0] = 0;
        for(int i = 1,j = 0; i < dest.length(); i++){
            while(j > 0 && dest.charAt(j) != dest.charAt(i)){
                j = next[j - 1];
            }
            if(dest.charAt(i) == dest.charAt(j)){
                j++;
            }
            next[i] = j;
        }
        return next;
    }
    public static void main(String[] args){
        String a = "ababacb";
        String b = "abababaababacb";
        int[] next = kmpnext(a);
        int res = kmp(b, a,next);
        System.out.println(res);
        for(int i = 0; i < next.length; i++){
            System.out.println(next[i]);            
        }
        System.out.println(next.length);
    }
}

• 前缀
• 后缀
• 最大共有长度
• next[ ]数组

Brute-Force(暴力)算法

1. 主串和模式串逐个字符比较
2. 当出现字符串不相同时，主串的比较位置重置为起始位置的下一个字符位置，模式串的比较位置重置为起始位置
3. 匹配成功后返回主串中匹配串的起始位置，否则就返回错误代码

缺点：在BF算法中，每次失配都需要回溯指向上次比较起始字符的下一个字符。算法的时间复杂度过高。

KMP算法

设计思想：一次失败并不可怕，从失败中累积经验，让自己前进的步伐更快，成功的几率更高！
———KMP (:з」∠)

待补充…