def BuildGST(pattern, suffix, GST): m = len(pattern) suffix[m-1] = m g = m-1 for i in range(m-2, -1, -1): if i > g and suffix[i+m-1-f] < i-g: suffix[i] = suffix[i+m-1-f] else: if i < g: g = i f = i while (g>=0 and pattern[g]==pattern[g+m-1-f]): g-=1 suffix[i] = f-g for i in range(0,m,1): GST[i] = m j=0 for i in range(m-1, -1, -1): if suffix[i] == i+1: while(j < m-1-i): if GST[j] == m: GST[j] = m-1-i j+=1 for i in range(0,m-1,1): GST[m-1-suffix[i]] = m-1-i def BuildBCT(pattern,BCT): for i in range(10000): BCT.append(-1) for i in range(len(pattern)): BCT[ord(pattern[i])] = i def search(pattern,GST,BCT,text): index = [] m = 0 t_len = len(text) p_len = len(pattern) i = p_len - 1 while m+i < t_len: if pattern[i] == text[m+i]: if i == 0: index.append(m) i = p_len-1 m += 1 i -= 1 else: m = m + max(GST[i], i-BCT[ord(pattern[i])]) i = p_len-1 return index if __name__=='__main__': pattern = input("Please input the pattern : ") print('\n') GST = [] BCT = [] suffix = [] leng = len(pattern) index_key = 0 for i in range(len(pattern)): GST.append(0) BCT.append(0) suffix.append(0) BuildGST(pattern, suffix, GST) BuildBCT(pattern,BCT) with open('source.txt') as f: line_number = 1 for line in f: cols = list(line) index = search(pattern,GST,BCT,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 |
'파이썬으로 구현한 알고리즘' 카테고리의 다른 글
| Regular Expression으로 전화번호 Search 구현하기 (0) | 2017.11.16 |
|---|---|
| Nested tree를 tree로 만들고 left child right sibling구조로 변환 구현하기 (0) | 2017.11.16 |
| KMP Algorithm 구현하기 (0) | 2017.11.11 |
| Priority Que 구현하기(우선순위 큐) (0) | 2017.09.25 |
| Linked list 구현하기 (0) | 2017.09.25 |