KMP算法Python/Java代码实现

关注我的微信公众号：后端技术漫谈

不定期推送关于后端开发、爬虫、算法题、数据结构方面的原创技术文章，以及生活中的逸闻趣事。

我目前是一名后端开发工程师。主要关注后端开发，数据安全，网络爬虫，物联网，边缘计算等方向。

原创博客主要内容

• Java知识点复习全手册
• Leetcode算法题解析
• 剑指offer算法题解析
• SpringCloud菜鸟入门实战系列
• SpringBoot菜鸟入门实战系列
• Python爬虫相关技术文章
• 后端开发相关技术文章

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);
 }
}