kmp added

code-lucidal58 · code-lucidal58 · commit eb24c60627c3 · 2020-05-18T09:32:53.000+05:30
diff --git a/README.md b/README.md
@@ -5,4 +5,4 @@ I am learning new algorithms and will be making notes for all of thoses here, al
 
 String matching algorithms
 * [Naive](./naive.py)
-* [KMP (Knuth Morris Pratt) Pattern Searching](./kmp.py)
+* [KMP (Knuth Morris Pratt)](./kmp.py)
diff --git a/kmp.py b/kmp.py
@@ -0,0 +1,44 @@
+"""
+KMP (Knuth Morris Pratt) Pattern Searching Algorithm is used for finding the indices of the presence of a given
+substring pattern in a string. It is an improvement on Naive.
+If you do not know the algorithm from beforehand, please watch this https://www.youtube.com/watch?v=V5-7GzOfADQ from 7:41
+Time Complexity: O(n) or O(n+m)
+"""
+
+
+def kmp(s: str, pat: str):
+    lps = [0] * len(pat)
+    i, l = 1, 0
+    while i < len(pat):  # create pi table
+        if pat[i] == pat[l]:
+            l += 1
+            lps[i] = l
+            i += 1
+        else:
+            if l != 0:
+                l = lps[l - 1]
+            else:
+                i += 1
+    i, j = 0, 0
+    indices = []
+    while i < len(s):
+        if s[i] == pat[j]:
+            i += 1
+            j += 1
+        else:
+            if j == 0:
+                i += 1
+            else:
+                j = lps[j-1]
+        if j == len(pat):
+            indices.append(i - len(pat))
+            j = lps[j-1]
+    return indices
+
+
+if __name__ == '__main__':
+    print(kmp("AABAACAADAABAABA", "AABA"))
+    print(kmp("AABCCAADDEE", "FAA"))
+    print(kmp("AAAAAAAAAAAAAAAAAA", "AAAAA"))
+    print(kmp("AAAAAAAAAAAAAAAAAB", "AAAAB"))
+    print(kmp("ABCDCDDDCDE", "ADE"))
diff --git a/naive.py b/naive.py
@@ -1,5 +1,5 @@
 """
-Naive algorithm is used for finding the indices of the presence of a given substring pattern in a string
+Naive algorithm is used for finding the indices of the presence of a given substring pattern in a string.
 Time Complexity O(m*(n-m+1)) or O(nm) where n and m are the lengths of string snd substrings respectively
 """
 
