문자열 - kmp 알고리즘

[1. 개요]

문자열 검색 문제

• 문자열 H 가 문자열 N 을 부분 문자열로 포함하는지 확인
• 포함한다면, N 과 일치하는 부분 문자열의 시작 위치를 찾는 문제
• N 이 H 에서 여러 번 출현한다면, N 이 출현하는 모든 위치를 반환해야 한다.

단순한 탐색 알고리즘의 경우 시간 복잡도는 O(|N| x |H|) 로, 

입력되는 문자열의 길이가 매우 긴 경우(그리고 특정 형태의 입력에 대해서),

꽤나 비효율적인 알고리즘 이지만, 현실적인 경우에서 그런 경우는 흔하지 않다.

 

KMP 알고리즘은 검색 과정에서 얻는 정보를 버리지 않고 활용하여,

동일한 문제에 대한 시간복잡도를 O(|N| + |H|) 로 상당히 개선할 수 있다.

---

[2. 알고리즘 원리]

KMP 알고리즘의 아래와 같은 특성을 이용한다.

• H[i...] 에서 N 을 비교 할 때, 글자 수가 L 개 까지 일치하고, L+1 부터 불일치가 발생했다고 하면,
• H 의 부분 문자열 H[i...i+L] 에서 가장 길게 접두사와 접미사가 일치하는 문자열의 길이만큼 점프하여
• 다음 탐색 위치로 잡는 것이다.

그래서 kmp 알고리즘에서는 찾고자 하는 문자열 N 에 대해서

H의 부분문자열과 비교하여, L 글자 수 만큼 일치했을 때, 

일치한 문자열에서 접두사도 되고 접미사도 되는 문자열의 최대 길이가 미리 계산되어 있어야 한다.

• p[i] = N[...i] 에서 접두사도 되고 접미사도 되는 문자열의 최대 길이
• 이러한 부분 일치 테이블이 미리 계산되어 있어야 한다.

---

[3. kmp 알고리즘 구현]

일단, 부분 일치테이블이 어떤 함수에 의해 계산되었다고 가정하고 진행해보면 아래와 같이 구현 할 수 있다.

---

[4. 부분 일치 테이블 계산]

부분 일치 테이블 역시 단순하게 구현할 수 있지만,

kmp 알고리즘을 응용하면, 더 빠른 시간복잡도를 갖도록 할 수 있다.

---

[5. 구현 시 주의사항]

getPartialMatch()

• begin 은 1부터 시작
• vector 에서 element 개수 주의
• begin+matched 는 index 로 사용 된다.

kmpSearch()

• begin 은 0부터 시작
• begin <= n-m 조건 ## begin+m <= n 
  => m 은 문자열의 길이, 등호가 필요하다.
• matched == 0 
  => ++begin
  => 한 글자도 일치하지 않았으므로, 다음 위치부터 비교
• begin 을 옮길 때,
  => 
• begin 을 옮긴 뒤, matched 도 부분 일치 테이블을 이용하여 바꿔 주어야 한다.
  => 접두사 만큼 접미사도 같으므로, 
  => 바뀐 위치의 접두사부터 다시 탐색 할 필요는 없다.

 

getPartialMatch() 구현을 기억하고 이를 토대로

kmpSearch() 구현을 작성하면 될 듯.