KMP법

• 브루트-포스법을 개선한 알고리즘으로 검사했던 위치 결과를 버리지 않고 이를 효율적으로 활용하는 알고리즘
• 텍스트와 패턴의 겹치는 부분을 찾아내어 검사를 다시 시작할 위치를 구함으로써 패턴을 최소의 횟수로 옮겨 알고리즘의 효율을 높인다.
• 몇 번째 문자부터 다시 검색할지에 대한 값을 미리 표로 만들어 둔다.
• 건너뛰기 표를 작성할 때는 패턴 안에서 중복되는 문자의 나열을 먼저 찾아나기 위해 패턴끼리 겹쳐놓고 생각하여 만든다.
• KMP법은 브루트-포스법보다는 복잡하고 Boyer-Moore법과는 성능이 같거나 좋지 않기 때문에 실제 프로그램에서는 거의 사용되지 않는다.

//KMP법에 의한 문자열 검색
 
static int kmpMatch(String txt, String pat) {
    int pt = 1;            //텍스트를 스캔하는 변수
    int pp = 0;            //패턴을 스캔하는 변수
    int[] skip = new int[pat.length() + 1];
    
    //건너뛰기 표
    skip[pt] = 0;
    while (pt != pat.length()) {
        if (pat.charAt(pt) == pat.charAt(pp)) {
            skip[++pt] = ++pp;
        } else if (pp == 0) {
            skip[++pt] = pp;
        } else {
            pp = skip[pp];
        }
    }
    
    //검색
    pt = pp = 0;
    while (pt != txt.length() && pp != pat.length()) {
        if (txt.charAt(pt) == pat.charAt(pp)) {
            pt++;
            pp++;
        } else if (pp == 0) {
            pt++;
        } else {
            pp = skip[pp];
        }
    }
    if (pp == pat.length()) {
        return pt - pp;
    }
    return -1;
}