Algorithms/KMP-Algorithm.py at main · 0ssm/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
# fast method Knuth-morris Algorithms
def KMP(t, p):
    n, m = len(t), len(p)
    if m == 0: return []
    lsp = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and p[i] != p[j]:
            j = lsp[j-1]
        if p[i] == p[j]:
            j += 1
        lsp[i] = j
    res = []
    j = 0
    for i in range(n):
        while j > 0 and t[i] != p[j]:
            j = lsp[j-1]
        if t[i] == p[j]:
            j += 1
        if j == m:
            res.append(i - m + 1)
            j = lsp[j-1]
    return res

# Usage
def solve():
    txt = "aabaacaadaabaaba"
    pat = "aaba"
    print(*(KMP(txt, pat)))
solve()


# Knuth-morris Algorithms // 2nd method
def LSP(pattern):
    m = len(pattern)
    lsp = [0] * m
    j = 0
    i = 1
    while i < m:
        if pattern[i] == pattern[j]:
            j += 1
            lsp[i] = j
            i += 1
        else:
            if j != 0:
                j = lsp[j - 1]
            else:
                lsp[i] = 0
                i += 1
    return lsp

def KMP(text, pattern):
    n = len(text)
    m = len(pattern)
    lsp = LSP(pattern)
    i = 0
    j = 0
    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1
        if j == m:
            print("Pattern found at index:", i - j)
            j = lsp[j - 1]
        elif i < n and pattern[j] != text[i]:
            if j != 0:
                j = lsp[j - 1]
            else:
                i += 1

def solve():
    txt = "aabaacaadaabaaba"
    pat = "aaba"
    s = KMP(txt, pat)
    return s
solve()