Skip to content

Instantly share code, notes, and snippets.

@simsicon

simsicon/kmp.py

Last active December 5, 2016 03:21
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save simsicon/a78698858bea3e7e28310378682bd30a to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save simsicon/a78698858bea3e7e28310378682bd30a to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. simsicon created this gist Aug 29, 2016.
    19 changes: 19 additions & 0 deletions kmp.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,19 @@
    def kmp(text, pattern):
    partial = [0]

    for i in range(1, len(pattern)):
    j = partial[i - 1]
    while j > 0 and pattern[j] != pattern[i]:
    j = partial[j - 1]
    partial.append(j + 1 if pattern[j] == pattern[i] else j)

    ret = []
    for i in range(len(text)):
    while j > 0 and text[i] != pattern[j]:
    j = partial[j - 1]
    if text[i] == pattern[j]: j += 1
    if j == len(pattern):
    ret.append(i - (j - 1))
    j = 0

    return ret