KMP 알고리즘

KMP 알고리즘을 배우기전 엄청 큰 문자열 더미에서 특정 문자열을 찾기 위해서는 아래와 같이 O(N*H)의 시간복잡도를 사용하여 찾았을 것이다.  N은 찾을려는 문자열 H는 문자열 더미이다.

for(int begin = 0; begin + N.size() <= 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);
}

예를 들어 H = "avadakedavra"에서 N = "aked"를 찾는 과정을 아래 사진으로 보여줍니다. 모든 상황을 비교하는 비효율적인 장면을 볼 수 있습니다.

이럴때 입력이 크면 꽤나 비효율적이지만 이런경우 흔치 않게 구현이 단순하기 때문에 표준라이브러리에 사용됩니다. C의 strstr(), C++ 문자열의 string::find(), 자바 문자열의 indexOf() 등이 이와같은 알고리즘을 사용합니다.

 

KMP 알고리즘

위와 다르게 검색 과정 중 얻는 정보를 버리지 않고 잘 활용하면 많은 시간을 절약할 수 있습니다. 

 

어떤 문자열에서 N="aabaabac"를 찾는 경우를 예로 생각해봅시다. 만일 aabaaba까지는 일치했지만 마지막 c가 일치하지 않는 경우 위와 같은 경우에는 한글자 옆으로 이동해서 반복하여 검색했습니다. 하지만 지금까지 일치하는 일곱 글자가 대응되었다는 사실을 이용하면 시작 위치 중 일부는 답이 될 수 없음을 보지 않아도 알 수 있기 때문입니다. 

위치 i에서 일곱 글자가 일치하기 위해서는 그림에서 볼 수 있듯이 H[i : i + 6]의 문자열이  aabaaba여야 합니다. i+1의 경우에는 한글자는 동일하지만 뒤에 글자가 틀려서 탈락. 결국 되는 것은 i+3, i+6 뿐입니다. 따라서 다음 확인 위치는 i+1이 아닌 i+3입니다. 

 

이와 같이 검색 과정에서 정보들을 미리 계산해 저장해 둘 수 있습니다. 이와 같은 문자열 알고리즘을 KMP 알고리즘이라고 합니다. 

 

다음 시작 위치 찾기

위 부분에서 검색 과정 중의 정보를 저장하여 한번 검색 후 빠르게 다음 검색으로 이동해야하는 데 다음 시작 위치는 어떻게 찾아야 하는지 알아 봅시다. 

 

시작점 i에서 matched까지 일치하고 마지막 글자에서는 틀렸습니다. matched 글자가 일치 했기 때문에 N의 접두사 N[matched-1]가 H[i:i+matched-1]와 일치했음을 알 수 있습니다. 

 

두 회색 부분의 글자가 같기 때문에 A와 B는 서로 일치함을 알 수 있습니다. 그러고 i + k가 답이 될 수 있으려면 B와 C도 서로 같아야 하므로 결과적으로 A와 C가 같아야합니다. 즉 결과적으로 C는 N[matched-1]의 접두사, A는 N[matched-1]의 접미사입니다. 

 

정리하자면 시작 위치 i+k에서 답을 찾기 위해서는 N[matched-1]의 길이 matched-k인 접두사와 접미사가 같아야합니다. 

그래서 빠르게 다음 위치를 찾기 위해서는 N의 각 접두사도 되고 접미사도 되는 문자열의 최대 길이를 구하면 됩니다. 

 

그래서 aabaaba의 경우에는 3만큼 옮김 aaba가 될 것입니다.

 

그래서 전처리 과정으로 pi[i] = N[...i]의 접두사도 되고 접미사도 되는 문자열의 최대 길이를 구하면 됩니다. 

 

KMP 알고리즘 구현

KMP 알고리즘은 시작위치 0에서 시작해서 H와 N의 글자를 비교합니다. 만약 matched 글자가 일치한 후 불일치가 발생했다면 시작점에  matched - pi[matched-1] 만큼 더해주면 됩니다. 

 

쉽게 설명하면 위 사진의 경우 현재 일치한 글자 수가 6개 입니다. 6개인데 접미사와 접두사가 동일한 가장 큰 길이는 4입니다. 

즉 matched - pi[matched-1]는 6  - 4가 되어서 시작점 i에 2만큼 추가하여 검색하면 됩니다. 그러고 다음 matched는 B와 C가 동일하기 때문에 4가되는 겁니다.

 

또한 하나도 일치하지 않는 경우에는 다음 글자부터 검색을 시작하면 됩니다. 

 

vector<int> KMPSearch(string base, string hook){
	int baseSize = base.size();
	int hookSize = hook.size();
	vector<int> ret;
	vector<int> pi = getPartialMatch(hook);

	int begin = 0, matched = 0; // 첫 글자부터 검색을 시작한다.
	while(begin <= baseSize-hookSize){
		if(matched < hookSize && base[begin+matched] == hook[matched]){
			matched++;
			if(matched == hookSize)
				ret.push_back(begin);
		}else{
			if(matched == 0) // matched가 0이면 다음 칸부터
				begin++;
			else{
				begin += matched - pi[matched-1];
				matched = pi[matched-1];	
			}
		}
	}

	return ret;
}

 

부분 일치 테이블 만들기 

접미사와 접두사가 동일한 최대길이 테이블 pi를 만들어보겠습니다. 여기서도 kmp 코드를 활용하여 pi를 구하겠습니다.

vector<int> getPartialMatch(string N){
	int m = N.size();
	vector<int> pi(m, 0);

	int begin = 1, matched = 0; // begin이 0이면 자기 자신을 찾는다.

	while(begin + matched < m){
		if(N[begin + matched] == N[matched]){ // begin에서 + matched뒤 matched는 앞 일치할 경우 
        //일치한 크기 삽입
			matched++;
			pi[begin+matched-1] = matched; 
		}else{
			if(matched == 0)
				++begin;
			else{
				begin += matched - pi[matched-1];
				matched = pi[matched-1];
			}
		}
	}

	return pi;
}

 

시간 복잡도 

위 KMPSearch의 경우 반복문이 base의 사이즈 만큼 한번 돌기 때문에 O(baseString) 부분 일치 테이블도 O(hookSize만큼 한번 돌기 때문에) 

 

O(base+hook)이된다.