[알고리즘]KMP 알고리즘

단순 문자열 비교

무식한 방법으로 문자열의 첫 글자부터 비교해 일치하는지 확인하는 방법
코드로 구현하면 아래와 같이 이중 for문으로 가능
시간복잡도는 O(NM)이 됨

public static int search(String text, String pattern) {
        for (int i = 0; i < text.length() - pattern.length() + 1; i++) {
            boolean flag = true;

            for (int j = 0; j < pattern.length(); j++) {
                if(text.charAt(i+j) != pattern.charAt(j)) flag = false;
            }
            
            if(flag) return i;
        }
        return -1;
    }

KMP 알고리즘

• 불일치가 발생한 텍스트 문자열의 앞부분에 어떤 문자가 있는지 사전에 파악이 가능하기 때문에,
  불일치가 발생한 앞부분에 대해서는 다시 비교하지 않으면서 매칭이 일어나는지 판단할 수 있는 알고리즘

• 패턴에 중복이 있을 경우에만 가능

• 시간복잡도는 O(N*M)

접두사와 접미사

KMP 알고리즘을 이해하려면 반드시 알아야하는 개념!

접두사는 문자열의 왼쪽에서부터, 접미사는 문자열의 오른쪽부터 시작해 차례로 한 개씩 더 읽어가며 만들 수 있음
경계란 접두사와 접미사가 같을 때의 그 접두사(=접미사)를 나타냄

pi배열

접두사와 접미사가 같은 부분 문자열 중 최대 길이를 나타낸 테이블을 미리 정의해줘야함.
이를 부분 일치 테이블이라고도 함.
어디까지가 일치하는지 알 수 있다면, 다음 시작 위치도 알 수 있음.

i	pattern(0...i)	접두사이면서 접미사인 최대 문자열	table[i]
0	a	없음	0
1	ab	없음	0
2	aba	a	1
3	abac	없음	0
4	abaca	a	1
5	abacaa	a	1
6	abacaab	ab	2
7	abacaaba	aba	3

위의 표에 나타낸 내용을 table이라는 배열에 저장하면 아래와 같다.

static int[] makeTable(String pattern) {
	int n = pattern.length();
	int[] table = new int[n];
		
	int idx=0;
	for(int i=1; i<n; i++) {
        // 일치하는 문자가 발생했을 때(idx>0), 연속적으로 더 일치하지 않으면 idx = table[idx-1]로 돌려준다.
		while(idx>0 && pattern.charAt(i) != pattern.charAt(idx)) {
			idx = table[idx-1];
		}
			
		if(pattern.charAt(i) == pattern.charAt(idx)) {
			idx += 1;
			table[i] = idx;  
		}
	}
	return table;
}

탐색 과정

1. 주어진 패턴에 대한 pi 테이블을 생성한다.
2. idx 변경하면서 전체 문자열에 대한 탐색 시작
   1) parent[i] == pattern[idx] && idx == pattern.length() -> 탐색 종료
   2) parent[i] == pattern[idx] 인 그 외의 경우 -> idx+=1
   3) idx > 0 && parent[i] != pattern[idx]
   -> idx-1의 pi테이블의 값을 이용해 중복되는 접두사 (접미사) 이후 부터 탐색을 다시 시작

1) i=0, idx=0

2) i=1, idx=1

3) i=2, idx=2

4) i=3, idx=3 불일치
idx = pi[idx-1] = table[2] = 1

5) i=4, idx=1
이전 탐색에서 불일치 되어도 idx=1부터 시작하는 이유는 table에서의 값이 1이기 때문에 접두사와 접미사가 같은 부분에서의 불필요한 탐색을 줄이기 위함이다.
즉, 이것이 KMP알고리즘이 빠르게 동작하는 이유이다.

6~7) i와 idx계속 증가

8) i=7, idx=5 불일치
→ idx =table[4] = 1

9) i=8, idx=1
-> table[4] = 1이었기 때문에 이전의 불일치 상황과 마찬가지로 idx=1부터 시작

10~ )idx=7이 된다면 모든 매칭되었다는 뜻이므로 탐색 종료

위의 과정을 코드로 나타내면 아래와 같다.

static void KMP(String parent, String pattern) {
	int[] table = makeTable(pattern);
		
	int n1 = parent.length();
	int n2 = pattern.length();
		
	int idx = 0; 
	for(int i=0; i< n1; i++) {
		while(idx>0 && parent.charAt(i) != pattern.charAt(idx)) {
			idx = table[idx-1];
		}
		if(parent.charAt(i) == pattern.charAt(idx)) {
			if(idx == n2-1) {
				idx =table[idx];
			}else {
				idx += 1;
			}
		}
	}
}