KMP에 대해 알아보자

  • 21/4/2022
  • 읽는 시간 2분

KMP

문자열 검색 알고리즘 중 접두사와 접미사를 구하는 알고리즘으로 naive 문자열 검색과 달리 문자열 전부를 검색하는 것이 아닌 접두사와 접미사가 같은 조건에 의해 만들어진 실패함수로 적절하게 인덱스를 조정하여 검색하는 알고리즘이다.

그림참고

실패함수

KMP 알고리즘에는 찾고자하는 문자열의 위치마다 별도의 실패 함수 값이 존재한다. 이 값은 불일치가 발생하였을 때 반복 인덱스가 어디로 이동해야 하는지 나타내는 값으로, 검색시에 틀린다고 무조건 찾는 문자열의 크기만큼 넘어가지 않게 하기 위한 장치이다. 이 함수로 만들어진 배열을 fail이라고 할 때 fail[x]가 가진 의미는 찾는 문자열의 처음 (x+1)글자 중, 일치하는 접두사/접미사 중 최대 길이다.

KMP 알고리즘에도 쓰이지만 접두사와 접미사 관련해서 필요한 경우 이 실패함수만 가져다가 사용하는 경우도 있다.

실패함수 소스

int fail[MAX] = {0,};
for (int i=1, j=0; i<S.length(); i++) {
	while(j < 0 && S[i] != S[j])
		j = fail[j-1];
	if(S[i] == S[j])
		fail[j] = ++j;
}

KMP 알고리즘

만들어진 실패 함수로 찾고자하는 문자열의 인덱스를 조정해줘서 대상 문자열과 찾고자하는 문자열의 글자들을 비교하며 찾아간다. 그리고 소스에서 보면 알겠지만 실패함수와 매우 흡사하다는 것을 알 수 있다. 이 말은 실패함수는 찾고자하는 문자열에 대해 KMP 알고리즘을 적용시켰다고 할 수 있다. 즉. KMP 알고리즘의 논리는 String에서 Word을 찾는다고 하면, 실패 함수는 Word에서 Word의 부분 문자열을 찾는다고 볼 수 있다. 이후 KMP에서는 if(S[i] == W[j])에서 찾은 뒤 원하는 동작을 넣어주면 된다.

KMP 알고리즘 소스

for(int i=0, j=0; i<N; i++){
	// 현재 글자가 불일치하면 fail 값을 계속 따라감
	while(j > 0 && S[i] != W[j]) j = fail[j-1];
	// 현재 글자가 일치
	if(S[i] == W[j]){
		// W를 S[i:i+M-1]에서 찾음
		if(j == M-1){
			// i=0부터 시작한다면 i-M+1. 문제 조건에 따라 1을 더함
			result.push_back(i-M+2);
			// 찾지 못한 것처럼 j를 이동시키면 됨
			j = fail[j];
		}
		else j++;
	}
}

문제

BOJ
찾기, Cubeditor, 시저 암호, 광고, 문자열 제곱

환형 문자열

환형 문자열이란 동그랗게 말린 원형 문자열을 뜻한다. 밑에 문제에서 볼 수 있겠지만, 룰렛이나 시계와 같이 동그란 물체에 문자열을 대입해서 해결하는 문제이다.

이 문제에 있어서는 KMP 알고리즘을 사용하는데 환형 문자열을 두 배로 늘리고 그 해당 문자열에 다른 문자열이 들어있나 체크해주면 된다. 이때 KMP 알고리즘을 사용한다.

시계 사진들, 속타는 저녁 메뉴

algorithm KMP

댓글