KMP 알고리즘(java) : 같은 문자열 몇개일까?

 

같은 문자열 찾기 알고리즘

ABABCBABABC 에서 ABAB가 몇번 나오는가? 일단 답은

ABABCBABABC로 2개

1번으로 단순하게는 ABABAB에서 한스텝씩 for루프를 돌려서 주어진 pattern과 일치하는지 비교할수 있다

단순 방식

ABABCB....에서 순차적으로 ABAB를 하나씩 비교해서 맞으면 count를 하나 올림,

그 다음으로 한칸 옮겨서 BABCB...에서 다시 비교하고 넘어가는 방식임

당연히 정답은 아님

 

해답은 KMP알고리즘을 통해 얻어와야 함(만든사람이 Knuth, Morris, Prett라서 앞글자 따서 이름지음)

KMP의 요점은 주어진 패턴에서 스킵할수 있는 정보가 있는지를 파악하고 이를 이용하여 비교 횟수를 최소한으로 하는것

 

가령 비교할 문자인 ABAB 에서 어떤 정보가 있는지있는지를 먼저 확인하고 그 정보를 이용해서 비교함

입력된 문자가 ABABC라고 하면 첫번째 위치에서 A B A B 한번 비교하고 그다음B로 위치를 옮겨서를 비교하는게 아니라 AB가 반복되는 3번째 A로 점프해서 C를 비교한다고 생각하면 된다.

이때 사용하는 정보가 비교문자 ABAB를 전처리해서 얻은 pi배열임

pi배열은 접두사와 접미사를 이용해서 얻을수 있다(앞글자들과 뒷글자가 같은 부분이 있는지)

접두사 접미사의 개념을 이해하기 위해 추가 설명을 하자면

 ABAB 는 앞글자부터 잘라보면 A , AB , ABA , ABAB 으로 부분으로 접두사들을 나열할수 있다

뒷글자부터 잘라보면 B, AB, BAB, ABAB로 접미사로 나열할수 있음.

 

이때 위 접두사들과 접미사가 같으면 스킵할수 있는 최대 길이 정보를 알수 있고 이를 pi 배열에 저장함

그럼 다시 pi배열은 어떻게 구할까

ABAB는 A , AB , ABA, ABAB로 나열할수 있는데

A는 p[0] = 0,

AB는 p[1] = 0,

ABA 는 A가 앞뒤(접두사 접미사)에 같기 때문에 1, p[2] = 1,

ABAB는 AB가 앞뒤(접두사 접미사)로 최대로 같은게 AB로 2, p[3] = 2,

이 전처리된 정보를 가지고 입력된 문자를 찾으면 됨

코드는

	public static int kmp(char[] str, char[] pattern) {
		int result =0;
		int[] pi = getPi(pattern);
		int strLength = str.length;
		int patterLength = pattern.length;
		int j = 0;
		for (int i = 0; i < strLength; i++) {
			while (j > 0 && str[i] != pattern[j]) {
				j = pi[j - 1];
			}
			if (str[i] == pattern[j]) {
				if (j == patterLength - 1) {
					result++;
					j = pi[j];
				} else {
					j++;
				}
			}
		}
		return result;
	}

	public static int[] getPi(char[] pattern) {
		int j = 0;
        int patterLength = pattern.length;
		int[] pi = new int[patterLength];
		for (int i = 1; i < patterLength; i++) {
			while (j > 0 && pattern[i] != pattern[j]) {
				j = pi[j - 1];
			}

			if (pattern[i] == pattern[j]) {
				pi[i] = ++j;
			}
		}
		return pi;
	}

 

추가로 getPi가 kmp의 루틴과 유사한데 pi를 얻는 것도 결국 문자에서 반복되는 값을 찾는것이므로 kmp의 원리를 이용해서 얻을수 있다