| 10 | |
| 11 | |
| 12 | def kmp(pattern, text, len_p=None, len_t=None): |
| 13 | # 1) Construct the failure array |
| 14 | failure = [0] |
| 15 | i = 0 |
| 16 | for index, char in enumerate(pattern[1:]): |
| 17 | if pattern[i] == char: |
| 18 | i += 1 |
| 19 | else: |
| 20 | i = 0 |
| 21 | failure.append(i) |
| 22 | |
| 23 | # 2) Step through text searching for pattern |
| 24 | i, j = 0, 0 # index into text, pattern |
| 25 | while i < len(text): |
| 26 | if pattern[j] == text[i]: |
| 27 | if j == (len(pattern) - 1): |
| 28 | return True |
| 29 | i += 1 |
| 30 | j += 1 |
| 31 | |
| 32 | # if this is a prefix in our pattern |
| 33 | # just go back far enough to continue |
| 34 | elif failure[j] > 0: |
| 35 | j = failure[j] - 1 |
| 36 | else: |
| 37 | i += 1 |
| 38 | return False |
| 39 | |
| 40 | |
| 41 | if __name__ == "__main__": |