KMP(Knuth-Morris-Pratt) 알고리즘

패턴의 접두사와 접미사를 이용한 부분일치 테이블을 만들어서 매칭이 실패했을 때 패턴 포인터가 돌아갈 인덱스 번호를 계산한다.

해당 테이블을 이용하여 만든 KMP 코드는 아래와 같다.

import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] sArr = br.readLine().toCharArray();
        char[] pArr = br.readLine().toCharArray();
        int sLen = sArr.length;
        int pLen = pArr.length;
 
        // 부분일치 테이블 배열 초기화
        int[] pi = new int[pLen];
        for (int i = 1, j = 0; i < pLen; i++) {
            while (j > 0 && pArr[i] != pArr[j])
                j = pi[j - 1];
            if (pArr[i] == pArr[j])
                pi[i] = ++j;
        }
 
        List<Integer> list = new ArrayList<>();
        for (int i = 0, j = 0; i < sLen; i++) {
            // 일치하지 않을 경우 j 위치 변경
            while (j > 0 && sArr[i] != pArr[j])
                j = pi[j - 1]; // j를 테이블의 이전 인덱스 pi값으로 설정
 
            if (sArr[i] == pArr[j]) { // 일치할 경우
                if (j == pLen - 1) { // 마지막 인덱스일 경우
                    list.add(i - pLen + 2);
                    j = pi[j]; // 현재 문자열에서의 부분일치 값을 j로 설정
                } else {
                    j++;
                }
            }
        }
        System.out.println("갯수 :  " + list.size());
        System.out.println("발견 인덱스 : " + list);
    }
}
 

 

부분일치 테이블은 sArr[i]와 pArr[j]가 다를 때 j-1까지의 문자와는 패턴이 일치한다는 원리를 기반으로 하고 있다.

그래서 j-1까지의 패턴 중 접두사와 접미사가 일치하는 문자의 수만큼은 다시 검사할 필요가 없기 때문에 해당 테이블의 값을 j의 새로운 인덱스로 설정하는 것이다.