공부/알고리즘

KMP, 라빈 카프 알고리즘

zzangyeah 2021. 6. 15. 16:43
728x90

백준 5525번 풀다가 모르겠어서 질문 검색란 보니 요런 알고리즘이 있길래 정리

https://www.acmicpc.net/problem/5525

 

5525번: IOIOI

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000)

www.acmicpc.net

문자열 검색 시 가장 간단한 방법을 생각해보자면 한자리씩 옮겨가면서 비교하는 방법이 떠오를 것

백준 문제를 예시로 들어보자

O O I O I O I O I I O I I
I O I                    
OOI!=IOI 불일치
O O I O I O I O I I O I I
  I O I                  
OIO!=IOI 불일치
O O I O I O I O I I O I I
    I O I                
IOI==IOI 일치!
O O I O I O I O I I O I I
      I O I              
OIO!=IOI 불일치

이런식으로 쭉쭉 진행

이렇게 하면 시간복잡도 O(문자열길이*패턴길이)가 됨

KMP 알고리즘

O(텍스트길이+패턴길이)에 해결가능