[기본문제풀이] KMP알고리즘

 

풀이 일시 : 2020-08-21

​

KMP알고리즘 :

Knuth Morris Pratt 알고리즘 / 대표적인 문자열(string)매칭 알고리즘

특정한 글이 있을 때 그 글 안에서 하나의 문자열을 찾는 알고리즘

​

문제1 :

일반 문자열 매칭 알고리즘 (KMP알고리즘 X)

​

풀이 :

BCDEF가 있고 그 중 DE를 찾을거면 자리를 하나씩 옮기며 비교하면서 매칭한다. O(N*M)

 

#include <iostream>

using namespace std;

int findString(string parent, string pattern) {
	int parentSize = parent.size();
	int patternSize = pattern.size();
	for (int i = 0; i <= parentSize - patternSize; i++) { // i : 시작 index 지칭
		bool finded = true; //finded를 true로
		for (int j = 0; j < patternSize; j++) { //패턴사이즈 내에서 돌면서 각각글자가맞는지
			if (parent[i + j] != pattern[j]) { //하나라도 맞지않으면
				finded = false; //finded를 false로
				break; //for문 빠져나온다.
			}
		}
		if (finded) { //true면 , 즉 모든 문자열이 다 맞는것
			return i; //1반환
		}
	}
	return -1; //안맞으면 -1반환
}

int main() {
	string parent = "Hello World";
	string pattern = "llo W"; //llo W
	int result = findString(parent, pattern);
	if (result == -1) {
		printf("찾을 수 없습니다.");
	}
	else {
		printf("%d번째에서 찾았습니다.", result + 1);
	}
	return 0;
}

 

문제 2 :

KMP알고리즘

​

풀이 :

KMP알고리즘을 사용하여 문자열 매칭을 확인한다.

- KMP 로 모든 경우를 다 비교하지 않아도 부분 문자열을 찾을 수 있다.

(접두사와 접미사의 개념을 활용하여 반복되는 연산을 얼마나 줄일수있는지 판별)

- 우리가 구해야 할 것은 접두사와 접미사가 일치하는 최대길이

abacaab 에서 접두사=접미사=ab 이다.

abacaaba 에서 접두사=접미사=aba이다

접두사와 접미사가 일치하는 경우에 한해서는 점프를 수행할 수 있다.

​

최대일치길이를 구하자

비교를 하다가 서로 다른 문자가 발견되면 일치하는 접두사 크기에 한해서 부분 문자열의 인덱스를 이동한다.

즉 매칭에 실패했을때 접두사 접미사 기준으로 얼마나 점프할수 있을지를 알려주는것이다.

실패했을때 현재 접두사와 접미사가 같다면 다음 접두사는 지금의 접미사 위치로 뛸수있다!!

​

=> ABCDABEDFS 에서 ABE를 찾고자할때 처음에 ABC와 비교를 하게되고 C와 E가 다르기때문에 맞지않다는 것을 알 수 있다. 여기서 (AB)는 동일하다는 단서를 놓치지 말자는 것을 알고리즘으로 구현한것

​

O(N+M)

 

#include <iostream>
#include <vector>

using namespace std;

vector<int> makeTable(string pattern) {
	int patternSize = pattern.size();
	vector<int> table(patternSize, 0); //크기 8이고 0으로 초기화
	int j = 0;
	for (int i = 1; i < patternSize; i++) {
		while (j > 0 && pattern[i] != pattern[j]) {
			j = table[j - 1];
		}
		if (pattern[i] == pattern[j]) {
			table[i] = ++j;
		}
	}
	return table;
}
// ababacabacaabacaaba로 테이블을 만들어보자
// table[0] 은 a로 따진다. 접두사 접미사 일치x = 0
// table[1] 은 ab로 따진다. 접두사 접미사 일치x = 0
// table[2] 는 aba로 따진다. 접두사 접미사 일치o = 1
// table[3] 은 abab로 따진다. 접두사 접미사 일치o = 2
//....
// 이후 이 테이블을 이용하여 뛰어넘을 수 있을것이다.

void KMP(string parent, string pattern) {
	vector<int> table = makeTable(pattern); //테이블생성 여기서는 abacaaba
	int parentSize = parent.size();
	int patternSize = pattern.size();
	int j = 0;
	for (int i = 0; i < parentSize; i++) {
		while (j > 0 && parent[i] != pattern[j]) {
			j = table[j - 1];
		}
		if (parent[i] = pattern[j]) {
			if (j == patternSize - 1) {
				printf("%d번째에서 찾았습니다.\n", i - patternSize + 2);
				j = table[j];
			}
			else {
				j++;
			}
		}
	}
}


int main() {
	string parent = "ababacabacaabacaaba";
	string pattern = "abacaaba";
	KMP(parent, pattern);
	return 0;
}