AlgoLab/Project1.py at master · johnleekj/AlgoLab · 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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
# -*- coding: utf-8 -*-
"""
Algo lab proj 1
"""

#Building prefix array for kmp
def buildarray(pattern):
    list = [0]
    j = 0
    found = False
    for i in range(1, len(pattern)):
        if (pattern[i] == pattern[j]):
            list.append(j+1)
            j += 1
        else:
            while j > 0:
                j -= 1
                j = list[j]
                if (pattern[i] == pattern[j]):
                    list.append(j+1)
                    j += 1
                    found = True
                    break
            if not found:
                list.append(0)
            else:
                found = False
    return list

def kmp(text, pattern):
    #text = "AAAAAAAAAA"
    #pattern = "AAA"
    prefix_arr = buildarray(pattern)
    pattern_i = 0
    for text_i in range(0, len(text)):
        if pattern[pattern_i] == text[text_i]:
            pattern_i += 1
            if pattern_i == len(pattern):
                found_index = text_i - len(pattern) + 1
                print("Pattern found at index: " + str(found_index))
                pattern_i = prefix_arr[pattern_i-1]

        else:
            while pattern_i > 0:
                pattern_i -= 1
                pattern_i = prefix_arr[pattern_i]
                if pattern[pattern_i] == text[text_i]:
                    pattern_i += 1
                    break

# prints all occurrences of pattern
# in text using Z algo
def searchZ(text, pattern):

    string = pattern + '$' + text
    z = [0] * len(string)

    n = len(string)

    l, r, k = 0, 0, 0

    for i in range(1, n):
        if i > r:
            l, r = i, i

            while r < n and string [r-l] == string[r]:
                r += 1
            z[i] = r - l
            r -= 1
        else:
            k = i-l

            if z[k] < r - i + 1:
                z[i] = z[k]

            else:
                l = i
                while r < n and string[r - l] == string[r]:
                    r += 1
                z[i] = r - l
                r -= 1

    for i in range(n):
        if z[i] == len(pattern):
            print("Pattern found at index", i - len(pattern) - 1)

def BruteForce_search(text, pattern):
    for x in range(len(text) - len(pattern) + 1):
        for y in range(len(pattern)):
            if(text[y+x] != pattern[y]):
                break
            if (y + 1 == len(pattern)):
                print("Pattern found at index " + str(x))

def main():
    filename = input("Please input file location:\n")
    filename = filename[1:len(filename)-1]
    #print(filename)
    genome_file = open(filename)
    genome_string = genome_file.read()
    genome_string = genome_string[genome_string.find('\n')+1:]
    pattern = input("Please input pattern to find:\n")
    #pattern = "TGACAGA"
    canloop = True
    while canloop: #easier to test algo
        print("--------------------------")
        print("Available algorithms")
        print("1.Brute Force")
        print("2.KMP")
        print("3.Z Algo")
        print("4.Enter another file location")
        select = input("Enter input 1-3\n") #Placeholder
        select = int(select)
        if (select == 1):
            BruteForce_search(genome_string, pattern)
        elif (select == 2):
            kmp(genome_string, pattern)
        elif (select == 3):
            searchZ(genome_string, pattern)
        elif (select == 4):
            filename = input("Please input file location:\n")
            filename = filename[1:len(filename)-1]
            genome_file = open(filename)
            genome_string = genome_file.read()
            genome_string = genome_string[genome_string.find('\n')+1:]
            pattern = input("Please input pattern to find:\n")
        else: #key in anything else to exit loop
            print("error")
            canloop = False


if __name__ == '__main__':
    main()