KMP, 라빈 카프 알고리즘

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

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

5525번: IOIOI

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

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

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(텍스트길이+패턴길이)에 해결가능