[Algorithm] KMP 알고리즘

KMP 알고리즘 ?

전체 문자열 : 문자열 전체

패턴 문자열 : 찾고 싶은 문자열

• 전체 문자열에서 일치하는 패턴 문자열을 찾아야 할 때 사용
• 패턴 문자열이 여러 번 존재할 수 있고 각각 어디 위치인지 찾아야 할 때
• 접두사, 접미사의 개념을 활용하여 반복되는 연산을 줄이고 매칭 할 문자열의 위치로 빠르게 점프

전체 시간복잡도 O(n+m) : n = 전체 문자열의 길이, m = 패턴 문자열의 길이

 

 

 

 

O(n^2)의 문자열 탐색 방식을 사용한 경우라면

 

for ( int i =0; i < 전체 문자열의 길이; i++) {

             // text[i] : 전체 문자열 중 i 번째 문자

             bool flag = true 

             for ( int j =0; j < 패턴 문자열의 길이; j++ ) {

                         // pattern[j] : 패턴 문자열의 j 번째 문자

                         if ( text[i+j] != pattern[j]) flag = false;

             }

             if (flag) 패턴 문자열 찾았다 !

}

 

탐색 중 text[i + j] 번째 문자와 pattern [j]가 일치하지 않는 경우 )) text[i+1] 과 pattern[0] 다시 비교

 

전체 문자열에 탐색한 부분을 반복해서 보고 싶지 않다

-> 필요한 정보를 저장해놓으면 시간을 줄일 수 있지 않을까 => 실패 함수

 

 

 

 

 

실패 함수 ?

• 전체 문자열의 i 번째 문자와 패턴 문자열의 j 번째 문자가 일치하지 않을 경우 패턴 문자열의 몇 번째 문자를 다시 비교해야 하는지 알려준다
• 패턴 문자열의 처음부터 j 번째까지의 범위를 가지는 부분 문자열에서 접두사와 접미사가 일치하는 최대 길이 값을 가지는 배열을 만든다

 

pi 배열 = 부분 문자열에서 접두사와 접미사가 일치하는 최대 길이 값을 가지는 배열

 

 

pi 배열을 만드는 실패 함수 코드

시간복잡도 O(m) : m = 패턴 문자열의 길이

 

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

 

 

 

 

 

KMP 알고리즘의 흐름 

1. 실패 함수를 통해 접두사와 접미사의 일치하는 최대길이를 저장한 배열 만들기
2. 실패 함수를 통해 만든 배열을 이용하여 전체 문자열과 패턴 문자열을 매칭

1 번은 위에서 해결 !

2 번 과정을 살펴보자

 

 

 

 

문자열 매칭 과정

 

• 전체 문자열의 인덱스 i 위치의 문자와 패턴 문자열의 인덱스 j 위치의 문자를 비교
  
  1. 두 문자가 같다면 )
     • j 와 i 모두 1씩 증가하여 다음 문자 비교
     • 이때 , j가 패턴 문자열의 마지막 글자라면 j = pi[j]
  2. 두 문자가 다르다면 )
     • j == 0 이 되거나 비교하는 두 문자가 같을 때 까지 반복 
       • j = pi [ j - 1 ]
       • 바뀐 j 위치에 대해 i 위치 문자와 다시 비교

 

 

 

문자열 매칭 과정 코드

시간복잡도 O(n+m) : n = 전체 문자열의 길이, m = 패턴 문자열의 길이

 

void KMP (string text, string pattern) {
	int j =0;
    auto pi = getPi(pattern);
    
    for (int i=0; i < text.size(); i++){
    	while (j > 0 && text[i] != pattern[j])
        	j = pi[j - 1];
        if (text[i] == pattern[j]) {
        	if (j == pattern.size() - 1)  //패턴 찾음
            	j = pi[j];
            else j++;
        }
    }
}

 

 

 

 

 

예시

끝

 

 

 

사진 출처 ) 김서울 엄마