KMP算法实现Python/Java

骑猪看日落 2022-05-29 04:14 183阅读 0赞

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

## 参考 ##

原理：  
[http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt\_algorithm.html][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][http_blog.csdn.net_christ1750_article_details_51259425]

Python：[http://blog.csdn.net/handsomekang/article/details/40978213][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)  
            while cur <= m-n: # 长度不够就终止  
                for i in range(n):  # 一次匹配长度  
                    if s[i+cur] != p[i]:  
                        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]) 
                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);
        }
    }

[http_www.ruanyifeng.com_blog_2013_05_Knuth_E2_80_93Morris_E2_80_93Pratt_algorithm.html]: http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
[http_blog.csdn.net_christ1750_article_details_51259425]: http://blog.csdn.net/christ1750/article/details/51259425
[http_blog.csdn.net_handsomekang_article_details_40978213]: http://blog.csdn.net/handsomekang/article/details/40978213