Knuth–Morris–Pratt algorithm, efficient single pattern searching algorithm.

Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def build(p):
    kmp = [0, 0]
    j = 0
    for i in range(1, len(p)):
        while j > 0 and p[i] != p[j]:
            j = kmp[j]
        if p[i] == p[j]:
            j += 1
        kmp.append(j)
    return kmp

def match(s, p):
    kmp = build(p)
    ans = []
    j = 0
    for i in range(len(s)):
        while j > 0 and s[i] != p[j]:
            j = kmp[j]
        if s[i] == p[j]:
            j += 1
        if j == len(p):
            ans.append(i - len(p) + 1)
            j = kmp[j]
    return ans

Exercises

1392. Longest Happy Prefix

using the KMP table.

1
2
3
4
5
6
7
8
9
10
11
def longestPrefix(self, s: str) -> str:
    nxt = [0, 0]
    j = 0
    for i in range(1, len(s)):
        while j > 0 and s[i] != s[j]:
            j = nxt[j]
        if s[i] == s[j]:
            j += 1
        nxt.append(j)
    
    return s[:nxt[-1]]

Reference

huahua