kmp altorithm

kmp알고리즘

문자열의 패턴 검색을 할 때 시간복잡도를 줄일 수 있는 알고리즘

시간복잡도 O(N+M)

N : 원본문자열 길이, M : 패턴문자열 길이

원리

문자열의 접두사들을 이용함

패턴을 비교할 때 패턴에서 이전 접두사들이 중복되어 패턴으로 나타나는 경우 이를 이용함

먼저 패턴에서 반복되는 부분을 검색한다.

예를 들어 패턴이 다음과 같다고 해보자

"ABCDABD"

이 경우 반복되는 위치를 표로 나타내면 다음과 같다.

A	B	C	D	A	B	D
0	0	0	0	1	2	0

5번째와 6번째에서 5번째는 1번째 패턴의 반복, 6번째는 1~2번까지의 패턴이 반복되는 것을 알 수 있다.

즉 반복되는 패턴의 시작 index를 나타내기 때문에 (접두사를 비교해서 같은경우) 해당 번째 까지는 비교를 더이상 수행하지 않아도 된다.

다음으로 검색할 문자열을 탐색한다.

문자열을 탐색하며 현재 번째 index와 일치할 경우 탐색을 이어나간다.

현재 번째 index와 일치하지 않는 경우, 현재 번째의 패턴 index에서, 이전 패턴 index (반복되는 접두사)가 있으면 그 index부터 비교한다.

만약 패턴이 완료된 경우 정답으로 추가하고, 패턴 index는 접두사가 같은 패턴의 시작점까지 이동한다.

vector<int> kmp(string& line, string& pattern) {
  int size = line.size(), pSize = pattern.size();
  vector<int> pIndexes(pSize, 0);

  vector<int> ret;

  // 패턴 인덱스 배열을 만듬
  for (int i = 1, pI = 0; i < pSize; i++) {
    while (pI > 0 && pattern[i] != pattern[pI]) {
      pI = pIndexes[pI - 1];
    }
    if (pattern[i] == pattern[pI]) {
      pI++;
      pIndexes[i] = pI;
    }
  }

  // 문자열을 순회하며 찾는 문자열들을 검색함
  for (int i = 0, pI = 0; i < size; i++) {
    while (pI > 0 && line[i] != pattern[pI]) {
      pI = pIndexes[pI - 1];
    }

    if (line[i] == pattern[pI]) {
      if (pI == pSize - 1) {
        ret.push_back(i - pSize + 1);

        pI = pIndexes[pI];
      } else {
        pI++;
      }
    }
  }

  return ret;
}