KMP

 

 

KMP Algorithm

Knuth-Morris-Pratt Algorithm

 

---

문자열 S와 T가 주어질 때

S가 T를 포함하는지 판단하는

문자열 검색 알고리즘

 

 

 

 

1. 문자열 T에 대한 pi 배열(size=M)을 구한다.

pi배열은 문자열 T 내의 반복된 문자열을 찾아 탐색 시간을 줄이는 데에 쓰인다.

pi[ i ] = k

⇔ T[ 0 ~ k ] = T[ i-k ~ k ]

⇔ T의 부분문자열(0~i)의 앞/뒤에서부터 길이 k인 부분문자열이 서로 같다.

	// Get pi
	int M = T.size();
	vector<int> pi(M, 0);
	for (int i = 1, j = 0; i < M; ++i) {
		while (j > 0 && T[i] != T[j]) j = pi[j - 1];

		if (T[i] == T[j]) pi[i] = ++j;
	}

 

 

 

2. 문자열 검색 진행

pi배열을 이용해 경우의 수를 줄여 검색할 수 있다.

 

	// KMP
	int N = S.size();
	vector<int> idx;
	for (int i = 0, j = 0; i < N; ++i) {
		while (j > 0 && S[i] != T[j]) j = pi[j - 1];

		if (S[i] == T[j]) {
			if (j == M - 1) idx.push_back(i - M + 2), j = pi[j];
			else j++;
		}
	}

• line 4: j=pi[j-1] T2(j=pi[6]=3) 참고
  
• line 7: i-M+2 = i-(M-1)+1
  같은 문자열이 존재하는 위치를 찾음 (i가 0부터라서 1 더함)
  문자열 존재 여부만 판단한다면 여기서 return true로 끝내도 된다. 
• line 7: j=pi[j] T1(j=pi[4]=2) 참고

 

 

 

 

 

 

KMP 문제들

7575 바이러스

1786 찾기

1893 시저암호

16570 앞뒤가 맞는 수열

 

 

 

 

문자열 너무 싫어서 KMP 매번 강의자료나 구글링 도움받았는데 너무 안일했던 것 같다.

이제 안 잊겠지 안 잊어야만 한다