update README

shengshijun · shengshijun · commit abc6fb2372bf · 2014-12-27T23:54:38.000+08:00
kmp算法
diff --git a/README.md b/README.md
@@ -45,8 +45,7 @@ algorithm
 ##字符串匹配算法
 1.  朴素算法
 2.  Rabin-Karp算法
-3.  有限自动机字符串匹配
-4.  KMP算法
+3.  KMP算法
 
 
 #数据结构
diff --git a/string/kmp.py b/string/kmp.py
@@ -0,0 +1,41 @@
+#!/usr/bin/env python
+# -*- coding:UTF-8
+__author__ = 'shenshijun'
+
+
+def match(origin, pattern):
+    origin_len = len(origin)
+    pattern_len = len(pattern)
+
+    def build_next():
+        _next_list = [0 for x in xrange(pattern_len)]
+        last_match = 0
+        for cur_index in xrange(1, pattern_len):
+            while last_match > 0 and pattern[last_match] != pattern[cur_index]:
+                last_match = _next_list[last_match]
+            if pattern[last_match] == pattern[cur_index]:
+                last_match += 1
+            _next_list[cur_index] = last_match
+        return _next_list
+
+    origin_index, pattern_index = 0, 0
+    next_list = build_next()
+    while origin_index < origin_len:
+        if pattern[pattern_index] == origin[origin_index]:
+            pattern_index += 1
+            origin_index += 1
+        while pattern_index > 0 and origin[origin_index] != pattern[pattern_index]:
+            pattern_index = next_list[pattern_index]
+        if pattern_index == pattern_len:
+            return origin_index - pattern_len
+
+
+def main():
+    print match("sb", 'sb')
+
+
+if __name__ == "__main__":
+    main()
+
+
+
