공부하는 식빵맘 👱‍♀️

공부하는 식빵맘 👱‍♀️

반갑습니다 :)

(C++) 문자열 검색 알고리즘 : KMP 알고리즘

Date:     Updated:

카테고리:

태그:

🚀 서론

🔥 쓰임새

어떤 글에서 원하는 문자열을 찾을 때 Ctrl + F 를 눌러 검색을 하곤 하는데, 이렇게 어떤 문자열에서 원하는 문자열을 검색할 때 그 검색어의 위치를 찾아주는 알고리즘이다.

  • “알고리즘” 단어를 검색한다면?
    • “KMP 알고리즘에 대해 배워봅시다. 알고리즘 공부 ~.~”

A 문자열에서 B 문자열을 검색한다면, A 문자열의 부분 문자열로서 B 문자열이 포함되어 있느냐! 라고 해석할 수 있다.


🔥 용어

KMP 알고리즘에 대해 정리하기에 앞서 몇 가지 용어를 정의하겠다.

  • 텍스트, text : 검색을 실행할 문자열. 이 문자열 내에 원하는 검색어가 있는지 탐색해보고자 함.
    • \(N\) : 텍스트의 길이
  • 검색어, search, pattern : 검색할 문자열. 검색이 된다면 텍스트 의 부분 문자열. 문자열 패턴 매칭을 하는 것과도 같기에 패턴이라고도 칭할 것.
    • \(M\) : 검색어의 길이


🔥 문자열 알고리즘 종류

  • 트라이 자료구조 \(O(M)\)
    • 검색 가능한 것
      • 1️⃣ 부분 문자열이 아닌 완전한 문자열, 2️⃣ 접두사
    • 문자열 중간에 있는 부분 문자열은 검색하기에 적합하지 않다. 오직 접두사 혹은 완전한 문자열만 검색 가능 (접미사의 경우 단어들 reverse 시킨 후 저장한 트라이에서 찾는 방법이 있음)
  • KMP 알고리즘 \(O(N + M)\)
    • 부분 문자열도 검색 가능
    • 텍스트 : 검색어 = 1 : 1 👉 텍스트 안에 검색하고자 하는 검색어가 하나 일 때 사용함
  • 아호 코라식 알고리즘 \(O(N + M_{1} + M_{2} + M_{3} +..)\)
    • 부분 문자열도 검색 가능
    • 텍스트 : 검색어 = 1 : N 👉 텍스트 안에 검색하고자 하는 검색어가 여러개일 때 사용함


🚀 단순하게 비교하는 방법들과의 비교

🔥 브루트 포스

image

텍스트의 모든 위치를 시작 위치로 삼은 후(정확히는 n - m 위치까지만 시작 위치로 삼는게 가능) 텍스트의 원소들과 검색어의 원소들을 차례 차례 비교한다. 일치하는한 계속해서 비교를 하고, 일치하지 않는 곳을 발견하는 순간 다음 시작 위치로 돌아가 다시 차례대로 비교를 한다.

예를 들어 텍스트 포인터가 i고, 검색어 포인터가 j라고 하자. i = 1 을 시작 위치로 삼았다면 i = 1 부터 시작하는 텍스트의 부분 문자열들의 원소와 검색어의 원소를 하나하나 비교하는 것이다. text[1] 과 search[0] 을 비교하고 text[2] 과 search[1] text[3]과 search[2] 을 비교하고 .. 이런식으로! 이렇게 비교해나가다가 일치하지 않는 곳을 처음으로 발견하면 이제 시작 위치는 i = 2가 되어 다시 text[2]로 되돌아가 text[2] 과 search[0] 을 비교하고 text[3] 과 search[1] 을 비교하고 .. 이렇게 또 반복한다.

이러한 단순 비교의 시간 복잡도는 \(O(NM)\)이 된다.

  • 이 방법의 아쉬운 점
    • 1️⃣ 상당한 시간 복잡도
      • 최악의 경우는 n - m + 1 개의 모든 시작 위치에서 시작한 비교가 항상 마지막 글자에서만 불일치가 발생했을 때인데 따라서 시간 복잡도는 \(O(M * (N - M + 1)) = O (NM)\) 이 된다.
      • 이는 어떤 페이지에서 10 글자의 어떤 단어를 검색하려 한다면 해당 페이지를 10 번이나 읽어야 한다는 말이기도 하다.
      • 텍스트(페이지)의 포인터는 검사를 하며 순회를 하다가도 불일치하는 원소가 발생하면 다음 시작 위치로 back 해버린다.
        • 예를 들어 text[3] 을 시작 위치로 text[10] 과 search[7] 을 비교하는데까지 왔더라도 여기서 불일치하면 text 포인터는 다음 시작위치인 text[4] 로 뒤돌아가버리고 여기서부터 다시 search의 첫 원소부터 차례차례 비교를 시작한다.
      • ⭐ KMP 알고리즘은 텍스트(페이지)를 딱 한번만 순회할 수 있도록, 즉 텍스트의 포인터가 단 한번도 뒤돌아가지 않고 앞만 보고 달려가는 O(N) 시간을 보장한다. (자세한 설명은 후술)
    • 2️⃣ 부분적으로나마 일치했던 정보는 그냥 버리고 있다.
      • text[3] 을 시작 위치로 text[10] 과 search[7] 을 비교하는데까지 왔더라도 여기서 불일치하면 text 포인터는 다음 시작위치인 text[4] 로 다시 돌아가야 한다고 예를 들었다. 생각해보면 text[3] ~ text[10] 까지는 검색어와 일치했었다는 의미이다. 그런데 불일치 되는 원소가 있었다고 해서 다음 시작 위치로 되돌아가는 바람에 text[3] ~ text[10] 까지는 검색어와 일치했었다는 이 정보를 그냥 버리게 된다.
      • ⭐ KMP 알고리즘은 그동안 일치했었던 정보를 활용한다. 그동안 일치했었던 앞의 부분 문자열의 접두사와 접미사가 일치하는 최대 길이를 활용한다. (자세한 설명은 후술)


🔥 검색어 길이 단위로 비교

image

image

텍스트의 포인터가 되돌아 가지 않고 \(O(N)\) 가 되도록 앞만 보고 증가만 한다고 가정해보자. 그러면 text[9]와 search[5] 에서 일치하지 않는다는 것을 알게 되었으니 text[10]과 검색어의 첫 글자인 search[0]부터 다시 비교를 하게 되는데 이러면 검색어 길이 단위로 뭉텅뭉텅 검사를 하게 되기 때문에 저렇게 중간에 답이 있는 경우는 찾아낼 수 가 없다. 텍스트의 포인터가 되돌아 가지 않게 할 수 있지만 이 방법은 올바른 답을 도출하지 못한다.


💡 특징

KMP 알고리즘은 브루트 포스 방법과 달리 현재까지 일치했었던 검색어의 부분 문자열 정보를 활용하므로 텍스트 포인터가 뒤돌아 가지 않고 선형으로 증가만 하기 때문에 시간 복잡도를 \(O(N)\) 으로 줄일 수 있는 알고리즘이다.

브루트 포스 방법으로는 불일치 하는 원소를 발견하게 된다면, 텍스트의 포인터는 다음 시작위치로 Back 하여 텍스트의 첫 원소부터 다시 일일이 검사를 하였었다. 그러나 불일치 하기 이전까지는 텍스트와 검색어의 원소들이 서로 일치했었다는 정보를 알고 있다. 이 정보를 활용한게 KMP 알고리즘이다. 그럼 어떻게 활용할까?

바로 이전까지 일치했었던 검색어 문자열에서 접두사와 접미사가 같은 것의 '최대 길이'를 미리 알아놓으면 된다는 것이다. 무슨 소리일까? 😮

image

text[4] 를 시작 지점으로 검색어(“ABDABB”)의 원소들과 “ABDAB” 부분 까지는 일치해왔었는데, 검색어의 마지막 글자인 “B” 에서 불일치가 발생했다고 가정해보자. 즉, 검색어의 6글자 중 앞의 5 글자 접두사는 일치한 것이다. 브루트포스 방법이였다면 다시 text[5] 를 시작지점으로 돌아간 후 검색어의 처음부터 비교를 다시 시작했을 것이다.

image

자세히 살펴보면 “ABDABB” 중, 앞에 일치했던 “ABDAB” 에서 A B D A B 이렇게 접두사 A B 와 접미사 A B 가 같다. 즉, 접두사와 접미사가 같은 부분이 있는 것이다! 또한 A B 는 이렇게 접두사와 접미사가 같은 부분의 최대 길이(2)가 된다. 이것 보다 더 긴 길이의 접두사 = 접미사 는 없다.

image

여태까지 일치했었던 검색어의 부분 문자열에서 접두사 = 접미사 의 최대길이를 활용하여 시간을 줄이는 방법

  • 접두사 = 접미사인 최대 길이(1 이상)을 활용한다면 다음 검사땐 search[0] 처음부터 검사할 필요가 없다.

“ABDAB” 에서 “AB” 는 접두사도 되고 접미사도 되기 때문에, 검색어를 굳이 처음부터 다시 검사할 필요 없이 A B 는 이미 일치했다고 치고 A B 의 다음 글자인 D 부터 검사하면 된다. 즉, “AB” 를 위와 같이 걸칠 수 있는 것이다. 앞서 5 글자가 일치했었던 상황에서 다시 검색어의 첫 글자부터 검사하며 “0 글자 일치” 상태로 돌아가지 않고, 이전에 텍스트에서 일치했었던 text[4]~text[8] “ABDAB” 의 접미사였던 “AB” 가 이제는 text[5] 부터 일치하기 시작한 문자열의 접두사가 될 수 있는 것이다. (접미사 = 접두사)이기 때문에! 따라서 새롭게 접두사가 된 “AB” 는 이미 일치했었던 정보로 치고, “2 글자 일치” 상태에서 자연스럽게 text[9] 와 search[2] 을 검사하면 되는 것이다.

위의 🔥 검색어 길이 단위로 비교 부분에서 \(O(N)\) 가 되기 위하여 텍스트 포인터가 감소하기 않고, 뒤 돌아가지 않고 앞만 보고 증가하도록 하면 중간에 있을지도 모르는 일치 문자열도 뛰어 넘어버리기 때문에 올바른 답을 도출하지 못한다고 하였는데, 이렇게 접두사 = 접미사의 길이를 활용하게 된다면, 텍스트의 새로운 부분 문자열을 검사할 떄도 접두사 = 접미사인 부분을 걸쳐놓고 이미 일치하다고 놓기 때문에 중간에 있을지도 모르는 일치 문자열 후보를 놓지지 않게 된다. 즉, 결론적으로 접두사 = 접미사를 활용하기 때문에 텍스트 포인터는 계속 선형으로 증가만 시키더라도 중간에 있을 답 후보들은 (접두사 = 접미사)인 부분으로 걸쳐놓기에 놓치지 않고 다 챙기게 될 수 있게 된 것이다.

이왕 걸치는거 최대로 걸치는게 좋으니 “최대 길이”를 찾는다.

image

  • 처음부터 일치 안할 때

위와 같이 text[i] 와 search[0] 첫 글자부터 일치하지 않을 때는 브루트 포스 방법과 똑같이 다음 시작 위치인 text[i + 1]로 텍스트 비교 시작위치를 옮기면 된다.

image

image

  • 그동안 접두사 = 접미사 없었을 때

“ABD” 검색어 중, “AB” 까진 일치했던 경우이다. 그러나 “AB” 는 접두사 = 접미사인 부분이 없다. 접두사의 종류는 “A” 뿐이고 접미사의 종류도 “B” 뿐인데 둘이 같지 않기 때문이다. 이러한 경우에는 소위 말해 걸칠만한게 없다.

이런 경우는 어쩔 수 없이 검색어의 첫 원소 search[0] 부터 다시 비교를 해야 한다. 그러나 앞에서도 언급하였듯이 텍스트 포인터가 다른 시작 위치로 돌아갈 필요는 없다. 그냥 선형으로 1 만큼 증가하여 바로 오른쪽 원소로 옮기면 될 뿐이다. 일치했었던 앞의 “AB” 정보만으로도 텍스트 포인터를 이제 “B” 로 놓고 다시 검사를 시작하더라도 어차피 일치 하지 않을 것이라는걸 알 수 있기 때문이다. 접미사 = 접두사인 부분은 없는데 “AB” 는 일치했었으니 이제 “B” (text[12])를 시작위치로 놓고 search[0]부터 비교해도 어차피 틀릴 것이라는 것을 알 수 있기 때문이다.

image

  • 이전 문자열에서 하나만 일치했을 때

염두해두어야 할 점이 있다면 “A” 의 접두사 = 접미사 인 부분은 없다는 것이다. 즉, “ABCD” 라는 문자열이 있다면 접두사와 접미사에 있어 문자열과 동일한 “ABCD” 는 접두사, 접미사로 고려하지 않는다. 만약 고려한다면 무조건 일치한 문자열 그 자체가 접두사 = 접미사의 최대 길이로 나올테니 KMP 알고리즘에 의하면 검색어 포인터에 변화가 없게 된다. 불일치 했으니 이제 다른 검색어 원소부터 다시 비교를 시작해야 하는데 앞에 일치했던 문자열들 전부가 걸칠 수 있는 문자열이라고 판단되는 것이나 마찬가지이기 때문이다. 따라서 해당 문자열과 동일한 문자열은 접두사와 접미사로 고려하지 않는다.

즉, “ABCD” 의 접두사는 “A”, “AB”, “ABC” 까지만, 접미사는 “D”, “CD”, “BCD” 까지만 고려한다는 것이다.

image

따라서 이렇게 “A” 하나만 일치했었던 것은 접두사 = 접미사 최대 길이가 0 이나 마찬가지이므로 다시 검색어의 첫 원소인 search[0] 부터 비교를 시작해나가면 된다.

image

  • 문자열 검색에 성공했을 때

처음으로 일치하는 것 하나만 찾고 끝낼 수도 있지만 검색 위치를 여러개 찾아내도 괜찮은 상황이라면, 이렇게 문자열 검색 하나에 성공했을 때 어떻게 해야 할까?

그냥 일치하지 않았을 때와 똑같이! 걸칠 수 있는 (접두사 = 접미사)의 최대 길이를 찾고 탐색을 계속 이어나가면 된다.

image

image

일치한 문자열이자 검색어인 “BBDABB” 에서 접두사 = 접미사의 최대 길이는 2 이므로, 이 2개를 걸쳐놓고 “2개는 일치 상태” 부터, 즉 search[2] 부터 비교를 시작하면 된다.

pi[i] 는 문자열의 i 인덱스까지의 부분 문자열에서 접두사 = 접미사의 최대 길이라고 정의하겠다.

  • “ABADAB”
    • pi[0] = 0
      • “A” 는 접두사 = 접미사인 부분이 없다.
    • pi[1] = 0
      • “AB” 는 접두사 = 접미사인 부분이 없다.
    • pi[2] = 1
      • “ABA” 는 접두사 = 접미사인 부분이 “A” 이다.
    • pi[3] = 0
      • “ABAD” 는 접두사 = 접미사인 부분이 없다.
    • pi[4] = 1
      • “ABADA” 는 접두사 = 접미사인 부분이 “A” 이다.
    • pi[5] = 2
      • “ABADAB” 는 접두사 = 접미사인 부분이 “AB” 이다.

전처리 과정에서, KMP 알고리즘으로 문자열을 검색하기 이전에 미리 위와 같이 인덱스별로 접두사 = 접미사의 최대 길이를 미리 구해놓아야 시간 복잡도면에서 효율적이다. 미리 접두사 = 접미사의 최대 길이 배열을 구해놓은 후 KMP 알고리즘으로 문자열을 검색하게 되는데, 이 “접두사 = 접미사의 최대 길이 테이블” 을 실패 함수라고 부르는 것 같다. 비교 결과 불일치로 판명되었을 때 사용하기 때문인 것 같다.

밑에서 자세히 설명을 하겠지만, 이 pi 테이블을 구하는 과정 또한 KMP 알고리즘으로 구할 수 있다. 이 과정은 문자열을 검색하기 전 전처리로 이루어져야 하는 과정으로 시간 복잡도는 \(O(M)\) 이 된다. 그래서 KMP 알고리즘의 총 시간 복잡도가 \(O(N + M)\) 이 되는 것이다.

용어 정리 한번 하고 넘어가도록 하겠다.

  • 접두사 = 접미사의 최대 길이 배열 를 뜻하는 용어
    1. 실패 함수
    2. LPS (Longest Prefix Suffix)
    3. Pi (Partial Match Table)


🚀 구현 코드 및 과정 설명

  1. Fail 함수로 미리 접두사 = 접미사의 최대 길이 배열 을 구해놓는다.
  2. 이를 활용하여 KMP 함수에서 KMP 알고리즘을 통해 문자열을 검색한다.
  • text : 검색하고자 하는 바탕 문자열
  • pattern : 검색어

KMP 알고리즘 구현 코드를 구글링하여 알아보니 대표적으로 두 가지 종류의 코드가 있는 듯 했다. 둘 다 코드만 봐서는 어떻게 굴러가고 동작하는지 내 머리로는 직관적으로 바로 이해가 되지 않았기 때문에..⭐ 두 코드의 작동 과정을 도식화해보며 이해하였다.

🔥 첫 번째 코드

#include <bits/stdc++.h>

using namespace std;

vector<int> Fail(string pattern) {
	int m = pattern.length();
	vector<int> pi(m); // partial match table

	pi[0] = 0;
	for (int i = 1, j = 0; i < m; i++) {
		while (j > 0 && pattern[i] != pattern[j])
			j = pi[j - 1];
		if (pattern[i] == pattern[j])
			pi[i] = ++j;
	}
	return pi;
}

vector<int> KMP(string pattern, string text) {
	int m = pattern.length(); 
	int n = text.length(); 
	vector<int> pos; 
	vector<int> pi = Fail(pattern); 

	for (int i = 0, j = 0; i < n; i++) {
		while (j > 0 && text[i] != pattern[j])
			j = pi[j - 1];
		if (text[i] == pattern[j]) { 
			if (j == m - 1) { 
				pos.push_back(i - m + 1);
				j = pi[j]; 
			}
			else j++; 
		}
	}
	return pos;
}

1️⃣ 검색 함수

검색 과정을 먼저 설명하기 위하여 이미 Fail 함수로 pi 배열을 모두 구해놓은 상태라고 가정하겠다.

vector<int> KMP(string pattern, string text) {
	int m = pattern.length(); // 검색어의 길이
	int n = text.length(); // 텍스트의 길이 
	vector<int> pos;  // 검색에 성공한 위치를 pos 에 저장할 것
	vector<int> pi = Fail(pattern); // 전처리 과정. pi 배열 구해놓기!

	for (int i = 0, j = 0; i < n; i++) {
		while (j > 0 && text[i] != pattern[j])// 일치 하거나 하나도 일치하는게 없는 상태(j = 0 (즉, 검색어 첫 글자부터 검사해야 하는 상태)가 될 때까지 계속해서 최대 길이의 접두사 = 접미사 부분의 접두사를 걸치자!
			j = pi[j - 1];
		if (text[i] == pattern[j]) { // 일치한다면 
			if (j == m - 1) { // 검색에 성공한 경우 (그 이전의 m - 1 개도 모두 일치. 총 m 개가 일치하는 셈)
				pos.push_back(i - m + 1); // 검색 성공한 일치 문자열의 시작 인덱스는 i - m + 1
				j = pi[j]; // j = pi[m - 1] 와 같음
			}
			else j++; // 일치하면 자연스레 검색어의 다음 원소 검사하러 가면 된다.
		}
	}
	return pos;
}

text[i] 와 pattern[j] 비교!

  • \(i\) : 텍스트 포인터(인덱스)
    • i++ 을 통해 1 씩 증가만 한다는 것에 주의!! \(O(N)\)
  • \(j\) : 검색어 포인터(인덱스)이자 이전까지 일치한 개수이기도 한다.
  • 이전에 하나라도 일치하는게 있었고 text[i] != pattern[j] 현재 일치하지 않는다면
    • 👉 이전까지 일치했던 것에서 최대 길이인 (접두사 = 접미사)로 걸치는 작업을 해주어야 한다.
      • 이제 검색어의 pi[j-1] (= 이전에 일치한 개수) 위치부터 검색할 수 있도록! (이전에 pi[j-1] 개는 이미 일치하였다고 판정되는 상태인 걸쳐놓은 상태로 시작)
  • 현재 일치 한다면
    • 검색에 성공한 경우
      • 이전에도 이미 m - 1개가 일치가 된 상태에서 현재 글자도 일치하게된 것이므로 검색어를 찾아내는데 성공한 경우가 된다. j == m - 1
      • 위에서 설명했듯이, 또 최대 길이인 (접두사 = 접미사)로 걸치고 다시 비교를 시작하면 된다. 다음부턴 검색어의 pi[m - 1] 위치에서부터 검사 시작
    • 아직 검색에 성공한건 아닌 경우
      • 자연스레 검색어의 다음 글자 검사하러 가면 된다. 이제 text[i+1] 과 pattern[j+1] 검사하러!
  • for
    • 텍스트 포인터 선형 증가 i++
  • while
    • 조건 👉 이전에 일치한게 1 개 이상이여야 하고 and 현재 비교 문자 일치하지 않음
    • 목적 👉 “걸치기” 작업 하기.
      • 더 이상 이전에 일치하는게 하나도 없어 걸칠게 없거나 현재 문자가 일치할 때까지 걸치기 작업을 실행한다.
      • 이 작업을 할 때 i 는 고정이다. text[i]는 고정.
  • if
    • 조건 👉 현재 비교 문자 일치할 때
    • 목적
      • 검색에 성공했다면 👉 “걸치기” 작업.
      • 아직 성공 X 👉 검색어의 다음 글자 비교하러 ㄱㄱ j++

image

노란 화살표는 텍스트 포인터(i), 초록색 화살표는 검색어 포인터(j)다.

  • while 문 ❌ (걸치기 작업 필요한데 j = 0 라 이전에 일치하는게 없어 걸칠게 없음)
  • if 문 ❌

image

  • while 문 ❌ (걸치기 작업 필요 없음)
  • if 문 ⭕
    • 더 검사 해야 함 : 검색어 포인터 1 증가

image

  • while 문 ❌ (걸치기 작업 필요 없음)
  • if 문 ⭕
    • 더 검사 해야 함 : 검색어 포인터 1 증가

image

  • while 문 ❌ (걸치기 작업 필요 없음)
  • if 문 ⭕
    • 더 검사 해야 함 : 검색어 포인터 1 증가

image

image

image

  • while 문 ⭕ (걸치기 작업 필요)
    • j = 3 (첫 번째 그림)
      • p[3-1] = p[2] = 1 (“ABA”의 LPS)
    • j = 1 (두 번째 그림)
      • p[1-0] = p[0] = 0 = “A”의 LPS
    • j = 0 (세 번째 그림)
  • if 문 ⭕
    • 더 검사 해야 함 : 검색어 포인터 1 증가

image

  • while 문 ❌ (걸치기 작업 필요 없음)
  • if 문 ⭕
    • 더 검사 해야 함 : 검색어 포인터 1 증가

image

  • while 문 ❌ (걸치기 작업 필요 없음)
  • if 문 ⭕
    • 더 검사 해야 함 : 검색어 포인터 1 증가

image

  • while 문 ❌ (걸치기 작업 필요 없음)
  • if 문 ⭕
    • 더 검사 해야 함 : 검색어 포인터 1 증가

image

  • while 문 ❌ (걸치기 작업 필요 없음)
  • if 문 ⭕
    • 더 검사 해야 함 : 검색어 포인터 1 증가

image

  • while 문 ❌ (걸치기 작업 필요 없음)
  • if 문 ⭕
    • 검색 성공! : j = p[5] = 2 (“ABADAB”의 LPS)

image

image

  • while 문 ⭕ (걸치기 작업 필요)
    • j = 2 (첫 번째 그림)
      • p[2-1] = p[1] = 0 (“AB”의 LPS)
    • j = 0 (두 번째 그림)
  • if 문 ⭕
    • 더 검사 해야 함 : 검색어 포인터 1 증가

image

  • while 문 ❌ (걸치기 작업 필요 없음)
  • if 문 ⭕
    • 더 검사 해야 함 : 검색어 포인터 1 증가

image

  • while 문 ❌ (걸치기 작업 필요 없음)
  • if 문 ⭕
    • 더 검사 해야 함 : 검색어 포인터 1 증가

image

  • while 문 ❌ (걸치기 작업 필요 없음)
  • if 문 ⭕
    • 더 검사 해야 함 : 검색어 포인터 1 증가

image

  • while 문 ❌ (걸치기 작업 필요 없음)
  • if 문 ⭕
    • 더 검사 해야 함 : 검색어 포인터 1 증가

image

  • while 문 ❌ (걸치기 작업 필요 없음)
  • if 문 ⭕
    • 검색 성공! : j = p[5] = 2 (“ABADAB”의 LPS)

i 가 n 에 도달하여 for문 종료.


2️⃣ 실패 함수 (partial match table)

  • 전처리로 문자열 검색 전 만들어 놓아야 할 테이블.
  • LPS 테이블 또한 KMP 알고리즘으로 만드는게 가능하다.

보통 검색어는 짧은 편이긴 하지만, 실패 함수(LPS 혹은 Pi) 테이블 또한 브루트 포스로 만들게 된다면 \(O(N^3)\) 이 되기 때문에 KMP 알고리즘으로 문자열을 검색하는 의미가 없다..

실패 함수를 만드는 과정 또한 KMP 알고리즘으로 만들 수 있다! 실패 함수 자체가 pattern[0] ~ pattern[i] 까지의 문자열에서 접두사와 접미사가 같은 최대 길이를 구하는 것이기 때문에 이 또한 KMP 알고리즘을 적용할 수 있는 것이다.

검색 함수와 달리 검색어와 검색어를 비교한다고 보면 된다. 동일한 검색어와 검색어의 글자들을 차례로 비교하면 검색어의 인덱스인 j 는 이전까지 일치한 문자의 개수를 뜻하기도 하므로, 비교하는 두 원소가 일치할 때마다 실패 함수 pi[i] 원소 값을 j 로 업데이트 하면 되는 것이다!

위 검색 함수와 약간만 다르다.

  • pi 의 모든 원소들 0 으로 초기화 한 후 시작.
  • 위에서도 언급했듯, pi[0]은 언제나 0 으로 친다. 그리고 pattern과 pattern을 비교하는 것이기에 둘 다 pattern[0] 부터 비교를 하면 모든 원소가 동일하다고 진행되고 끝나게 되기 떄문에 pattern[0]과 pattern[1] 을 비교하는 것에서부터 시작을 하도록 한다.
  • 검색 함수와 달리 현재 비교 문자가 일치할 땐 (if 문)
    • 1️⃣ ++j j 를 1 증가시킨다.
      • 일치한 개수 늘었으니깐! 이건 검색함수 에서도 해주는 과정이다.
    • 2️⃣ pi[i] = j
      • 같은 검색어끼리 비교를 하고 있기에, search[0] ~ search[i] 현재까지 일치한 개수는! 텍스트 역할 하고 있는 검색어의 “접미사”와 검색어 역할 하고있는 검색어의 “접두사” 가 일치한 그 접두사 = 접미사의 길이와도 같다.
      • 이것 자체 만으로 현재 (i)까지의 최대 길이가 된다. (그러므로 딱히 max 연산을 해줄 필요는 없다.)
vector<int> Fail(string pattern) {
	int m = pattern.length();
  // partial match table 
	vector<int> pi(m); // 모든 원소가 0 으로 초기화된 상태에서 시작한다.

	for (int i = 1, j = 0; i < m; i++) {
		while (j > 0 && pattern[i] != pattern[j])
			j = pi[j - 1];
		if (pattern[i] == pattern[j])
			pi[i] = ++j; // j 를 1 만큼 증가시킨 후, pi 업데이트
	}
	return pi;
}

image

search[0] 과 search[1] 비교부터 시작!

  • while 문 ❌ (걸치기 작업 필요한데 j = 0 라 이전에 일치하는게 없어 걸칠게 없음)
  • if 문 ❌

image

  • while 문 ❌ (걸치기 작업 필요 없음)
  • if 문 ⭕
    • pi[2] = 1

image

image

  • while 문 ⭕ (걸치기 작업 필요)
    • j = 1 (첫 번째 그림)
      • p[1-1] = p[0] = 0 (“AB”의 LPS)
    • j = 0 (두 번째 그림)
  • if 문 ❌

image

  • while 문 ❌ (걸치기 작업 필요 없음)
  • if 문 ⭕
    • pi[4] = 1

image

  • while 문 ❌ (걸치기 작업 필요 없음)
  • if 문 ⭕
    • pi[5] = 2

image


🔥 두 번째 코드

#include <bits/stdc++.h>

using namespace std;

vector<int> Fail(string pattern) {
	int m = pattern.length();
	vector<int> pi(m); // partial match table

	int begin = 1;
	int matched = 0;
	pi[0] = 0;
	while (begin + matched < m) {
		if (pattern[begin + matched] == pattern[matched]) {
			matched++;
			pi[begin + matched - 1] = matched;
		}
		else {
			if (matched == 0)
				begin++;
			else {
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}
	return pi;
}

vector<int> KMP(string pattern, string text) {
	int m = pattern.length();
	int n = text.length();
	vector<int> pos;
	vector<int> pi = Fail(pattern);

	int begin = 0;
	int matched = 0;
	while (begin + m <= n) {
		if (matched < m && text[begin + matched] == pattern[matched]) {
			matched++;

			if (matched == m)
				pos.push_back(begin);
		}
		else {
			if (matched == 0)
				begin++;
			else {
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}
	return pos;
}

1️⃣ 검색 함수

vector<int> KMP(string pattern, string text) {
	int m = pattern.length();
	int n = text.length();
	vector<int> pos; // 검색에 성공한 위치를 pos 에 저장할 것
	vector<int> pi = Fail(pattern); // 전처리 과정. pi 배열 구해놓기!

	int begin = 0;    // 📌 Text 에서 일치하기 시작한 "시작" 포인터
	int matched = 0;  // 📌 일치한 개수이자 검색어의 포인터
	while (begin <= n - m) { // begin 은 n - m 까지만 가능 (ex. n=7, m=3 이라고 할 때 begin 은 4까지만 될수 있다. 4,5,6 이렇게 3개 끝!
    // 💛아직 성공하지 않았고 and 일치한다면
		if (matched < m && text[begin + matched] == pattern[matched]) { 
			matched++; // 일치한 개수 + 1, 검색어의 다음 글자 검사하러! 

			if (matched == m) // 혹시 검색 성공 했다면
				pos.push_back(begin);
		}
    // 💛성공 했거나 일치하지 않는다면 (걸치는 작업 필요)
		else {
      // 근데 이전까지 일치한게 하나도 없었다면 걸칠게 없다. 
			if (matched == 0)
				begin++; // text[begin] 텍스트 원소와의 비교는 틀렸기 때문에 이제 text[begin+1] 부터 또 일치하기 시작하는지 검사
      // 이전까지 일치한게 있었다면 걸칠 수 있음
			else { 
				begin += matched - pi[matched - 1]; // 일치하기 시작한 포인터는 begin 이였는데 begin + matched 에서 불일치가 일어났고 일치하는 이전 문자열 중 pi[matched - 1] 길이만큼은 접두사 = 접미사이기 때문에 이제 begin + matched 에서 pi[matched - 1] 만큼만 뒤로간 곳을 일치하기 시작한 새로운 포인터 begin 으로 삼는다.
				matched = pi[matched - 1]; // 걸쳤기 때문에 pi[matched - 1] 개는 일치한 상태에서 시작하게 된다.
			}
		}
	}
	return pos;
}

text[begin + matched] 와 pattern[matched] 비교!

빨간색은 begin 포인터를 의미한다.

  • \(begin\) : 텍스트에서 일치하기 시작한 "시작" 포인터 (첫 번째 코드 \(i\)와 다른 점)
    • 1 씩 증가하는건 아니지만, 역시 계속 증가만 하지 감소하지는 않는다.
  • \(matched\) : 이전까지 일치한 개수이자 검색어의 포인터

image

begin = 0, matched = 0, begin[0] 와 search[0] 비교

  • else 일치 ❌
    • 이전까지 일치한 것도 하나도 없다.
      • begin 1 증가 (현재의 begin 은 이전까지 일치한 문자열의 시작 포인터가 될 수 없다. 일치하지 않았으니까!)

image

begin = 1, matched = 0, begin[1 + 0] 와 search[0] 비교

  • if 아직 성공하지 않았고 일치 ⭕
    • matched 1 증가

image

begin = 1, matched = 1, begin[1 + 1] 와 search[1] 비교

  • if 아직 성공하지 않았고 일치 ⭕
    • matched 1 증가

image

begin = 1, matched = 2, begin[1 + 2] 와 search[2] 비교

  • if 아직 성공하지 않았고 일치 ⭕
    • matched 1 증가

image

begin = 1, matched = 3, begin[1 + 3] 와 search[3] 비교

  • else 일치 ❌
    • 앞에 일치했던게 1 개 이상이다.
      • 이전까지 일치했었던 matched = 3 개 (“ABA”) 👉 pi[3] = 1
        • begin = 1 + 3 - 1 = 3
        • matched = 1

image

begin = 3, matched = 1, begin[3 + 1] 와 search[1] 비교

  • else 일치 ❌
    • 앞에 일치했던게 1 개 이상이다.
      • 이전까지 일치했었던 matched = 1 개 (“A”) 👉 pi[0] = 0
        • begin = 3 + 1 - 0 = 4
        • matched = 0

image

begin = 4, matched = 0, begin[4 + 0] 와 search[0] 비교

  • if 아직 성공하지 않았고 일치 ⭕
    • matched 1 증가

image

begin = 4, matched = 1, begin[4 + 1] 와 search[1] 비교

  • if 아직 성공하지 않았고 일치 ⭕
    • matched 1 증가

image

begin = 4, matched = 2, begin[4 + 2] 와 search[2] 비교

  • if 아직 성공하지 않았고 일치 ⭕
    • matched 1 증가

image

begin = 4, matched = 3, begin[4 + 3] 와 search[3] 비교

  • if 아직 성공하지 않았고 일치 ⭕
    • matched 1 증가

image

begin = 4, matched = 4, begin[4 + 4] 와 search[4] 비교

  • if 아직 성공하지 않았고 일치 ⭕
    • matched 1 증가

image

begin = 4, matched = 5, begin[4 + 5] 와 search[5] 비교

  • if 아직 성공하지 않았고 일치 ⭕
    • matched 1 증가

image

begin = 4, matched = 6, matched == m 성공한 상태

  • else 성공한 상태
    • 앞에 일치했던게 1 개 이상이다.
      • 이전까지 일치했었던 matched = 6 개 (“ABADAB”) 👉 pi[5] = 2
        • begin = 4 + 6 - 2 = 8
        • matched = 2

image

begin = 8, matched = 2, begin[8 + 2] 와 search[2] 비교

  • else 일치 ❌
    • 앞에 일치했던게 1 개 이상이다.
      • 이전까지 일치했었던 matched = 2 개 (“AB”) 👉 pi[2] = 0
        • begin = 8 + 2 - 0 = 10
        • matched = 0

image

begin = 10, matched = 0, begin[10 + 0] 와 search[0] 비교

  • else 일치 ❌
    • 이전까지 일치한 것도 하나도 없다.
      • begin 1 증가

image

begin = 11, matched = 0, begin[11 + 0] 와 search[0] 비교

  • if 아직 성공하지 않았고 일치 ⭕
    • matched 1 증가

image

begin = 11, matched = 1, begin[11 + 1] 와 search[1] 비교

  • if 아직 성공하지 않았고 일치 ⭕
    • matched 1 증가

image

begin = 11, matched = 2, begin[11 + 2] 와 search[2] 비교

  • if 아직 성공하지 않았고 일치 ⭕
    • matched 1 증가

image

begin = 11, matched = 3, begin[11 + 3] 와 search[3] 비교

  • if 아직 성공하지 않았고 일치 ⭕
    • matched 1 증가

image

begin = 11, matched = 4, begin[11 + 4] 와 search[4] 비교

  • if 아직 성공하지 않았고 일치 ⭕
    • matched 1 증가

image

begin = 11, matched = 5, begin[11 + 5] 와 search[5] 비교

  • if 아직 성공하지 않았고 일치 ⭕
    • matched 1 증가

image

begin = 11, matched = 6, matched == m 성공한 상태

  • else 성공한 상태
    • 앞에 일치했던게 1 개 이상이다.
      • 이전까지 일치했었던 matched = 6 개 (“ABADAB”) 👉 pi[5] = 2
        • begin = 11 + 6 - 2 = 15
        • matched = 2

image

begin + m (=15+6) 이 텍스트의 범위인 n (17) 이상이 되어버렸기 때문에 종료한다.


2️⃣ 실패 함수 (partial match table)

vector<int> Fail(string pattern) {
	int m = pattern.length();
	vector<int> pi(m); // partial match table

	int begin = 1;   // 📌 접두사 역할을 하는 검색어에서 일치하기 시작한 "시작" 포인터
	int matched = 0; // 📌 접미사 역할을 하는 검색어의 일치한 개수이자 포인터
	pi[0] = 0;
	while (begin + matched < m) {
		if (pattern[begin + matched] == pattern[matched]) {
			matched++;
			pi[begin + matched - 1] = matched;
		}
		else {
			if (matched == 0)
				begin++;
			else {
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}
	return pi;
}

역시 검색함수와 거의 비슷하다. 검색어와 검색어끼리의 KMP 알고리즘을 돌린다.

  • 성공 여부를 따지지 않아도 되며 (pos 삽입이라던가, matched < m 검사하는 것)
  • 일치하다면 현재의 matched 는 접두사 = 접미사의 현재까지(정확히는 begin+matched-1 에서) 최대 길이가 되는 것과 같다.
  • 역시나 첫 번째 코드와 마찬가지로, search[1] 부터 검사를 한다.
    • 즉, begin 은 1 에서 시작

image

begin = 1, matched = 0, begin[1 + 0] 와 search[0] 비교

  • else 일치 ❌
    • 이전까지 일치한 것도 하나도 없다.
      • begin 1 증가

image

begin = 2, matched = 0, begin[2 + 0] 와 search[0] 비교

  • if 아직 성공하지 않았고 일치 ⭕
    • matched 1 증가

image

begin = 2, matched = 1, begin[2 + 1] 와 search[1] 비교

  • else 일치 ❌
    • 앞에 일치했던게 1 개 이상이다.
      • 이전까지 일치했었던 matched = 1 개 (“A”) 👉 pi[1] = 0
        • begin = 2 + 1 - 0 = 3
        • matched = 0

image

begin = 3, matched = 0, begin[3 + 0] 와 search[0] 비교

  • else 일치 ❌
    • 이전까지 일치한 것도 하나도 없다.
      • begin 1 증가

image

begin = 4, matched = 0, begin[4 + 0] 와 search[0] 비교

  • if 아직 성공하지 않았고 일치 ⭕
    • matched 1 증가

image

begin = 4, matched = 1, begin[4 + 1] 와 search[1] 비교

  • if 아직 성공하지 않았고 일치 ⭕
    • matched 1 증가

image


🚀 시간 복잡도

텍스트 포인터는 앞만 보고 달려간다. 감소하지 않으며 늘 1 씩 선형시간으로 증가한다.

  • \(O(N)\) : 검색 함수
  • \(O(M)\) : 실패 함수
  • 결론적으로 \(O(N + M)\)


📌 Reference


🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Algorithm 카테고리 내 다른 글 보러가기

댓글 남기기

최근 글 10 개 :)