1. 단순한 알고리즘

   // H 문자열에서 N의 부분 문자열을 탐색한다. 
   vector<int> naiveSearch(const string& H, const string& N) {
   	vector<int> ret; 
   
   	for (int begin = 0; begin < H.size(); begin++) {
   		bool matched = true;
   		for (int i = 0; i < N.size(); i++) {
   			if (H[begin + i] != N[i]) {
   				matched = false;
   				break;
   			}
   		}
   		if (matched) ret.push_back(begin);
   	}
   	return ret; 
   }
   

   단순하게 전체 문자열의 모든 부분을 순회하면서 부분 문자열이 있는지 확인하는 방식이다. 이 방식은 구현이 간단하지만, aabbbbaa에서 aabbba를 찾는 것과 같이 마지막만 다른 경우에도 앞의 비교를 모두 수행한다는 점에서 비효율적이다.

2. KMP 알고리즘

   H에서 N 부분수열을 찾는 과정 중, 앞 단계에서 이미 탐색한 부분에 대해 그 뒤의 단계에서 다시 탐색을 수행한다는 단점이 있다.

   이를 부분 일치 테이블을 이용해 해결한다. 이전 단계에서 어디까지 일치했는지 탐색하고, 다음 단계에서 다음 시작 위치를 어디로 할 지 미리 계산해두는 것이다.

   이전 단계에서 불일치를 확인했다고 하자. 불일치를 감지하기 이전의 문자의 위치를 matched라고 했을 때, 다음에 얼만큼 떨어진 곳(k) 에서 탐색을 시작할 지 찾기 위해서 아래 로직을 사용한다.

   

   matched에서 글자가 마지막으로 일치한 후 불일치가 발생하였다고 할 때, 다음 시작 위치는 matched-pi[matched-1]이다.

   #include <iostream>
   #include <vector>
   using namespace std;
   
   vector<int> getPartialMatch(const string &N);
   
   // H의 부분 문자열로 N이 출연하는 모든 시작 위치를 반환
   vector<int> kmpSearch(const string& H, const string& N) {
   	int n = H.size(), m = N.size();
   	vector<int> ret; 
   	// pi[i] = N[..i]의 접미사도 되고 접두사도 되는 문자열의 최대 길이
   	vector<int> pi = getPartialMatch(N);
   
   	int begin = 0, matched = 0;
   	while (begin <= n - m) {
   		
   		if (matched < m && H[begin + matched] == N[matched]) {
   			matched++; 
   			// 모든 문자가 일치한다면 해당 시작 위치를 ret에 넣는다. 
   			if (matched == m) ret.push_back(begin);
   		}
   		else {
   			if (matched == 0)
   				begin++;
   			else {
   				begin += matched - pi[matched - 1];
   				matched = pi[matched - 1];
   			}
   		}
   	}
   	return ret;
   }
   

   begin을 바로 다음부터 할 게 아니라, 마지막으로 일치한 지점에서의 부분 문자열 pi[..matched]까지 중에서 접두사도 되고 접미사도 되는 최대 길이의 문자열 만큼 뺀 길이만큼 증가하여 새롭게 시작하는 것이다.

   부분 일치 테이블을 완성해보자.

   vector<int> getPartialMatch(const string& N) {
   	int m = N.size();
   	vector<int> pi(m, 0); 
   
   	for (int begin = 1; begin < m; begin++) { // 시작점을 순회
   		for (int i = 0; i + begin < m; i++) { // 시작점을 기준으로 문자열 순회
   			if (N[begin + i] != N[i]) break;
   
   			// i + 1 글자가 서로 대응되었다. 
   			pi[begin + i] = max(pi[begin + i], i + 1);
   		}
   	}
   	return pi;
   }
   

   지금 pi[i], 즉 N[..i] 위치에서 접두사도 되고, 접미사도 되는 문자열의 최대 길이를 반환하고자 한다.

   여기서 for문 조건이 왜 아래와 같이 되었는 지 의문이 들 수도 있다. 아래 그림을 참고하면, begin지점을 처음부터 끝까지 옮겨가며, 그 지점 이후의 문자열을 탐색하며 접미사와 접두사를 검사하는 알고리즘이기 때문이다.

   for (int begin = 1; begin < m; begin++) 
   		for (int i = 0; i + begin < m; i++)
   

   

   대충 뭐 요런 ..

예제 : 접두사/접미사

예제 : 팰린드롬 만들기

아래는 전통적인 KMP 알고리즘이다.

vector<int> kmpSearch(const string& H, const string& N) {
	int n = H.size(), m = N.size(); 
	vector<int> ret; 
	vector<int> pi = getPartialMatch(N);

	int matched = 0;
	for (int i = 0; i < n; i++) {
		while (matched > 0 && H[i] != N[matched])
			matched = pi[matched - 1];

		if (H[i] == N[matched]) {
			matched++; 
			if (matched == m) {
				ret.push_back(i - m + 1);
				matched = pi[matched - 1];
			}
		}
	}
	return ret; 
}

KMP 알고리즘 복습하기

문제 : 재하의 금고

접미사 배열

어떤 문자열이 있을 때, 이 문자열의 모든 접미사를 사전순으로 저장해 둔 자료구조이다.

특정 문자열을 찾고자 하면, 해당 위치에서 시작하는 접미사들을 비교하는 것으로 탐색이 시작된다.

// 두 접미사의 시작 위치가 주어질 때, 어느 접미사가 앞에 와야하는 지 결정한다.
struct SuffixComparator {
	const string& s;
	SuffixComparator(const string& s) : s(s) {};
	bool operator() (int i, int j) {
		return strcmp(s.c_str() + i, s.c_str() + j) < 0;
	 // s + i가 s + j보다 더 작음. 
	}
};

// s의 접미사 배열을 검사한다.
vector<int> getSuffixArrayNaive(const string& s) {
	vector<int> perm;
	for (int i = 0; i < s.size(); i++) perm.push_back(i);
	// 접미사를 비교하는 비교자를 이용해 정렬한다. 
	sort(perm.begin(), perm.end(), SuffixComparator(s));
	return perm;
}

접미사 배열을 생성한 방법이다.