반응형
34강에 대한 리뷰
대표적인 문자열 매칭 알고리즘
모든 경우를 비교하지 않아도 부분 문자열을 찾아줌
접두사와 접미사의 개념을 활용함: 접두사와 접미사가 일치하는 최대 길이를 구함
** Python
def make_table(pattern):
pattern_len = len(pattern)
table = [0 for i in range(pattern_len)]
j = 0
for i in range(1, pattern_len):
while j != 0 and pattern[i] != pattern[j]:
j = table[j - 1]
if pattern[i] == pattern[j]:
j += 1
table[i] = j
return table
if __name__ == "__main__":
p = "abacaaba"
t = make_table(p)
print(t)
def make_table(pattern):
pattern_len = len(pattern)
table = [0 for i in range(pattern_len)]
j = 0
for i in range(1, pattern_len):
while j != 0 and pattern[i] != pattern[j]:
j = table[j - 1]
if pattern[i] == pattern[j]:
j += 1
table[i] = j
return table
def kmp(parent, pattern):
table = make_table(pattern)
parent_len = len(parent)
pattern_len = len(pattern)
j = 0
for i in range(parent_len):
while j > 0 and parent[i] != pattern[j]:
j = table[j - 1]
if parent[i] == pattern[j]:
if j == (pattern_len - 1):
print(f'{i - pattern_len + 2} 번째에서 찾았습니다')
# print(i - pattern_len + 2)
j = table[j]
else:
j += 1
if __name__ == "__main__":
pr = "ababacabacaabacaaba"
pt = "abacaaba"
# t = make_table(pt)
# print(t)
kmp(pr, pt)
반응형
'Algorithm > 알고리즘 스터디(2021.07)' 카테고리의 다른 글
[Algorithm] 그리디 알고리즘 (Greedy Algorithm) (0) | 2021.11.29 |
---|---|
[Algorithm] 라빈 카프 알고리즘 (0) | 2021.11.29 |
[Algorithm] 단순 문자열 매칭 알고리즘 (0) | 2021.11.22 |
[Algorithm] 위상정렬 문제풀이 (0) | 2021.11.16 |
[Algorithm] 이분 매칭 (Bipartite Matching) (0) | 2021.11.01 |