[알고리즘 정리] KMP(3/3)

이전 포스트에서 pi 배열을 구해봤습니다. 이제 텍스트에서 pi 배열을 사용해 패턴을 찾아냅니다.

패턴을 찾아내는 과정은 pi 배열을 만드는 과정과 똑같습니다. 다만, i가 1부터 시작하는 것이 문자열의 시작인 0부터 시작합니다.

---

---

---

---

---

---

---

---

---

j가 패턴 길이의 끝에 도착하면, 패턴이 발견된 것입니다. 문자열 순회가 아직 끝나지 않았으므로, 패턴이 발견된 이후부터 다시 검사를 시작합니다. 이 때, pi[j] 는 1이므로, 인덱스 1부터 새로 검사를 시작하면 됩니다.

---

---

---

---

---

---

---

---

---

---

---

---

---

아래 함수는 위의 패턴 매칭 과정을 구현한 코드입니다.

static void KMP(String text, String patttern) {
	int[] pi = getPi(pattern);
	char[] orgin = text.toCharArray();
	char[] pt = pattern.toCharArray();

	int j = 0;
	for (int i = 0; i < text.length(); i++) {
		while (j > 0 && origin[i] != pt[j]) {
			j = pi[j - 1];
		}

		if(origin[i] == pt[i]) {
			if (j == pattern.length() - 1) {
				// 패턴을 찾았습니다. 여기서 검출 작업을 합니다.
				j = pi[j]; // 다음 매칭을 검사하기 위해서 j는 마지막 부분으로 돌아갑니다.
			}
			else {
				j++;
			}
		}
	}
}