KMP 알고리즘(문자열 찾기)

KMP 알고리즘이란?

우리가 문서에서 컨트롤+F눌러서 문자를 검색하던 항상 쓰였던 알고리즘이다.

알고리즘을 어떻게 구현하였을지 단순히 생각해보면 당연히 모든 인덱스에서 한번씩 패턴을돌려보는

N이 텍스트의 길이,M이 패턴의 길이라고 할 때 O(N*M)을 생각할 것이다.

하지만 KMP알고리즘은 O(N+M)정도로 줄여준다

 

 

KMP알고리즘에는 두가지 함수가 필요하다

전처리 테이블

 

KMP알고리즘은 접두사와 접미사를 기반으로 만드는 전처리 테이블이 필요하다

 

 

접두사와 접미사 같을때의 최대길이를

저장해주는 것이다

 

 

 

 

 

 

코드로 구현하면 다음과 같다.

KMP 함수구현

이렇게 전처리 테이블을 만들면 이제 테이블을 활용하여 겹치는 부분들을 활용하여 j는 순서대로 돌지만 i를 테이블값에 따라 빙빙 돌리면 된다

그림으로 보면

3번 인덱스에서 i와 j값이 틀렸다.

그러면 패턴에서 돌고있는 변수 i에 대해서 i-1값의 테이블값 인덱스를 찾아간다. table[2]의 값은 aba이므로 1일 것이다.

 

 

 

1의 인덱스는 b이므로 현재 j값 b와 같다.

i은 1부터 돌고 j는 변함없이 돈다.

 

 

 

 

위 과정들은 사실 table만들 때와 비슷하다. i를 계속 괴롭혀주면된다.

다르게 나온곳 인덱스-1 의 테이블값에 들어가서 

겹쳤던 부분들과 비교하며 추적해 가는 과정이다.

i=table[i-1]로 text[j]와 pattern[i]가 같을때까지 반복될것이다

 

 

 

 

 

 

다음과 같이 패턴 인덱스가 끝까지왔는데 모두 일치했다?

그럼 그때의 인덱스 j에서 패턴의 길이를 빼주고 1을 더해주면 일치하는 부분을 찾았을 때의 인덱스를 얻을 수 있다.

이 때는 찾을 것을 찾은것이지 값이 다른게 아니므로 i=table[i]로 바꿔줘야된다고 생각할 수 있다.table[7]=3이므로 3

(abacaaba가 성공했다고 맨뒤로 넘기면 뒤에서 3번째 aba부터 다시 시작되서 생기는 값을 놓칠수있다)

이 코드는 밑에 문제에 KMP함수 부분이다

 

1786 찾기

www.acmicpc.net/problem/1786

1.접근

KMP알고리즘으로 답을 찾을때마다 정답 배열에 넣어준다

2.코드

3.배운점

• 이해하기 정말 힘든 알고리즘이였다.i값을 계속 돌리는게 어렵다
• table만드는 것과 kmp돌리는 함수가 만드는게 비슷하다는 걸 기억하자

출처: https://bowbowbow.tistory.com/6 [멍멍멍]

출처: blog.naver.com/ndb796/221240660061