KMP算法实现Python/Java

kmp算法的核心时间复杂度就是O（m+n）

参考

原理：
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

Java：http://blog.csdn.net/christ1750/article/details/51259425

Python：http://blog.csdn.net/handsomekang/article/details/40978213

Python

    #KMP
    def kmp_match(self, s, p):  
        m = len(s)
        n = len(p)  
        cur = 0  # 起始指针cur  
        table = self.partial_table(p)  
        # print(table)
        while cur <= m-n: # 长度不够就终止  
            # print("新一轮匹配，开始位置", cur)
            for i in range(n):  # 一次匹配长度  
                if s[i+cur] != p[i]:  
                    # print(s[i+cur], p[i], '不匹配。查表位置：', i, i - table[i-1])
                    cur += max(i - table[i-1], 1) # 有了部分匹配表,我们不只是单纯的1位1位往右移,可以一次移动多位  
                    break  
            else:
                return cur 
        return -1  

    #部分匹配表  
    def partial_table(self, p):  
        '''''partial_table("ABCDABD") -> [0, 0, 0, 0, 1, 2, 0]'''  
        prefix = set()  
        table = [0]  
        for i in range(1, len(p)):  # 从1开始进行前后缀比较  
            prefix.add(p[:i])  # 前缀每次累加就行
            postfix = set()
            for j in range(1, i+1):  # i+1 因为i需要包括
                postfix.add(p[j:i+1]) 
            # print(prefix, postfix)
            # print(prefix&postfix, len(prefix&postfix))
            # table.append(len((sorted((prefix&postfix),key = len)or {''}).pop()))
            if prefix&postfix:
                table.append(max(map(len,prefix&postfix)))
            else:
                table.append(0)
        return table  

Java

Java的来自网络，有空理解下，实现table似乎原理不同

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 = "aabaaac";
        String b = "aabaaabaaac";
        int[] next = kmpnext(a);
        int res = kmp(b, a, next);
        System.out.println("result:" + res);
        for(int i = 0; i < next.length; i++){
            System.out.println("table:" + next[i]);            
        }
        System.out.println(next.length);
    }
}