패턴매칭
[알고리즘] 패턴 매칭 알고리즘 소스코드
- 한번만 찾는 경우 # 패턴이 있을 수 있는 가능한 시작 위치 for i in range(n-m+1): # 패턴의 길이 만큼 비교 for j in range(m): # 일치하지 않으면 다음으로 넘어감 if p[j] != t[i+j]: break else: # 매칭 성공 break - 모든 패턴을 찾을 때 : 방법1 i = 0 while i
[알고리즘] 문자열 패턴 매칭
패턴 매칭에 사용되는 알고리즘 고지식한 패턴 검색 알고리즘(=Brute Force) 카프-라빈 알고리즘 KMP 알고리즘 보이어-무어 알고리즘 고지식한 패턴 검색 (Brute Force) 문자열을 처음부터 끝까지 차례대로 순회, 패턴 내의 문자들을 일일이 비교 텍스트에서 패턴이 존재하는 모든 위치를 찾는 문제 시간복잡도 : O(MN) M: 패턴의 길이, N: 텍스트의 길이 최악의 경우 텍스트의 모든 위치에 대해 패턴을 비교해야 함 패턴 매칭 알고리즘의 중요 포인트 일치하는 경우 ( t[i] == p[j] ) i, j를 증가시켜서 다음 문자를 비교 불일치하는 경우 다음 매칭의 시작위치로 i, j 값을 설정 ※ 자주 사용되는 대치어 텍스트 패턴 기본 t p 인덱스 i j 길이 m n KMP 알고리즘 불일치가 ..