[C++] KMP 알고리즘

KMP 알고리즘이란 ?

---

최대 접두부를 구현하여 불일치를 감지할 때마다 이전의 일치 문자열로 돌아가 점프하는 방식으로

시간 복잡도는 최악의 경우 O(N) : 문자열 길이 * 패턴 길이

 

 

[ 구성 요소 ]

lps[] : 패턴 문자열에서 접두사와 접미사가 일치하는 최대길이 저장

pattern[] : 패턴 문자열

text[] : 주어진 문자열

---

 

KMP 알고리즘 함수 구현하기

---

 

예시 문자열 ) ABAABAB

i	문자열	lps[i]
0	A	0
1	AB	0
2	ABA	1
3	ABAA	1
4	ABAAB	2
5	ABAABA	3
6	ABAABAB	2

=> lps에 최대길이인 3이 들어감

 

lps 구현 코드​

void lps_array(string pattern, int M, int lps[]) {
    int len = 0; //접두사
    lps[0] = 0;

    int i = 1; //접미사
    while(i < M) {
        if(pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if(len != 0) len = lps[len-1];
            else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

 

 

간단한 동작 방식

	0	1	2	3	4	5	6
	A	B
i위치		i
len위치	len		=> i != len && len==0이므로 lps[1]=0, i++
	A	B	A
i위치			i
len위치	len		=> i==len이므로 len++, lps[2]=1(len값), i++
	A	B	A	A
i위치				i
len위치		len	=>i!=len && len!=0이므로 len=lps[len-1] 즉, len=lps[0]=0 왜냐면 그전까지는 일치함을 기억하기때문에 돌아감

 

==> KMP Algorithm함수와 같은 원리!!

 

KMP 함수 구현 코드

void KMP(string pattern, string text) {
    int M = pattern.size();
    int N = text.size();

    int lps[M];
    lps_array(pattern, M, lps);

    int i = 0, j = 0;

    while(i < N) {
        if(pattern[j] == text[i]) {
            j++;
            i++;
        }

        if(j == M) {
            j = lps[j-1];
        }else if(i < N && pattern[j] != text[i]) {
            if(j != 0) j = lps[j-1];
            else i = i+1;
        }
    }
}

 

 

(참고)

https://bblackscene21.tistory.com/2

[알고리즘 공부] KMP Algorithm (문자열 검색 알고리즘)