def make_kmp_table(pattern,border): m= len(pattern) border[0] = -1 border[1] = 0 i = 2 cnd = 0 while(i < m): if pattern[i-1] == pattern[cnd]: cnd += 1 border[i] = cnd i += 1 elif cnd > 0: cnd = border[cnd] else: border[i] = 0 i += 1 def kmp_search(pattern, border, text): index = [] m = 0 i = 0 t_len = len(text) p_len = len(pattern) while m+i < t_len: if pattern[i] == text[m+i]: if i == p_len-1: index.append(m) i = 0 m += 1 i += 1 else: if border[i] > -1: m = m + i- border[i] i = border[i] else: i = 0 m += 1 return index if __name__=='__main__': pattern = input("Please input the pattern : ") print('\n') border = [] leng = len(pattern) index_key = 0 for i in range(len(pattern)): border.append(0) make_kmp_table(pattern,border) with open('source.txt') as f: line_number = 1 for line in f: cols = list(line) index = kmp_search(pattern,border,cols) if index: for index_target in index: index_target = index_target + index_key cols.insert(index_target,'[[') cols.insert(index_target+leng+1,']]') index_key += 2 index_key = 0 print(line_number,index,"------") for k in cols: print(k,end='') print('\n') line_number += 1 | cs |
'파이썬으로 구현한 알고리즘' 카테고리의 다른 글
| Regular Expression으로 전화번호 Search 구현하기 (0) | 2017.11.16 |
|---|---|
| Nested tree를 tree로 만들고 left child right sibling구조로 변환 구현하기 (0) | 2017.11.16 |
| Boyer-Moore Algorithm 구현하기 (0) | 2017.11.11 |
| Priority Que 구현하기(우선순위 큐) (0) | 2017.09.25 |
| Linked list 구현하기 (0) | 2017.09.25 |