|
1 | | -/* |
2 | | - Knuth Morris Prath String Search algorithm Implementation |
3 | | -*/ |
4 | | - |
5 | | -package kmp |
6 | | - |
7 | | -//Table Building Algorithm |
8 | | - |
9 | | -func preKMP(T *[]int, pat string) { |
10 | | - |
11 | | - var i = 0 |
12 | | - var j = -1 |
13 | | - (*T)[0] = -1 |
14 | | - length := len(pat) - 1 |
15 | | - |
16 | | - for i < length { |
17 | | - for j > -1 && pat[i] != pat[j] { |
18 | | - j = (*T)[j] |
19 | | - |
20 | | - } |
21 | | - i++ |
22 | | - j++ |
23 | | - |
24 | | - if pat[i] == pat[j] { |
25 | | - (*T)[i] = (*T)[j] |
26 | | - |
27 | | - } else { |
28 | | - (*T)[i] = j |
29 | | - } |
30 | | - } |
31 | | - |
32 | | -} |
33 | | - |
34 | | -//search kmp |
35 | | -func Search(str, pat string) int { |
36 | | - |
37 | | - n := make([]int, len(pat)) |
38 | | - //preprocessing |
39 | | - preKMP(&n, pat) |
40 | | - |
41 | | - m := 0 //the beginning of the current match in str |
42 | | - i := 0 //the position of the current character in pat |
43 | | - |
44 | | - for { |
45 | | - if m+i > len(str) { |
46 | | - break |
47 | | - } |
48 | | - |
49 | | - if pat[i] == str[m+i] { |
50 | | - i++ |
51 | | - if i == len(pat) { |
52 | | - //an occurence was found we return it |
53 | | - return m |
54 | | - } |
55 | | - } else { |
56 | | - if n[i] > -1 { |
57 | | - m = m + i - n[i] |
58 | | - i = n[i] |
59 | | - |
60 | | - } else { |
61 | | - m = m + i + 1 |
62 | | - i = 0 |
63 | | - } |
64 | | - |
65 | | - } |
66 | | - } |
67 | | - return -1 |
68 | | -} |
| 1 | +TEXT = "but it's exactly these questions that allow me to find an answer fast if I'm just 'looking it up' on google." |
| 2 | +print("TEXT:" , TEXT) |
| 3 | +print("Pattern :") |
| 4 | + |
| 5 | +PATTERN = input() # Enter the Pattern to be searched |
| 6 | + |
| 7 | +def KMP(text, pattern): |
| 8 | + found_it = False |
| 9 | + match = False |
| 10 | + check_from = 0 |
| 11 | + sp_index = getIndex(pattern) |
| 12 | + for i in range(0, len(text)): |
| 13 | + for j in range( check_from, len(pattern)): |
| 14 | + if(text[i] == pattern[j]): |
| 15 | + match = True |
| 16 | + i+=1 |
| 17 | + else: |
| 18 | + match = False |
| 19 | + break |
| 20 | + if match == False: |
| 21 | + check_from = sp_index[j -1] |
| 22 | + else: |
| 23 | + print("Found '" + str(pattern) + "' at Position " + str(i-j)) |
| 24 | + found_it = True |
| 25 | + break |
| 26 | + |
| 27 | + if not found_it: |
| 28 | + print("No Match Found") |
| 29 | + |
| 30 | +def getIndex(pattern): |
| 31 | + sp_index = [0,] |
| 32 | + j = 0 |
| 33 | + for i in range(1, len(pattern)): |
| 34 | + if pattern[j] == pattern[i]: |
| 35 | + j += 1 |
| 36 | + sp_index.append(j) |
| 37 | + else: |
| 38 | + while(j > 0): |
| 39 | + j = j-1 |
| 40 | + j = sp_index[j] |
| 41 | + if pattern[j] == pattern[i]: |
| 42 | + j += 1 |
| 43 | + break |
| 44 | + sp_index.append(j) |
| 45 | + return sp_index |
| 46 | + |
| 47 | +import timeit |
| 48 | + |
| 49 | +start = timeit.timeit() # Start Time |
| 50 | +#Start Search |
| 51 | +KMP(TEXT, PATTERN) |
| 52 | +end = timeit.timeit() # End Time |
| 53 | +print("Time Taken:" + str(end)) |
0 commit comments