문자열 매칭 — KMP 알고리즘과 실패 함수의 원리

// 브루트포스 — O(N × M)
public int bruteForce(String text, String pattern) {
    int n = text.length(), m = pattern.length();
    for (int i = 0; i <= n - m; i++) {
        int j = 0;
        while (j < m && text.charAt(i + j) == pattern.charAt(j)) {
            j++;
        }
        if (j == m) return i; // 매칭 성공
    }
    return -1;
}

패턴: A B A B D
인덱스: 0 1 2 3 4

pi[0] = 0  "A" → 접두사=접미사 없음
pi[1] = 0  "AB" → 없음
pi[2] = 1  "ABA" → "A" = "A" (길이 1)
pi[3] = 2  "ABAB" → "AB" = "AB" (길이 2)
pi[4] = 0  "ABABD" → 없음

pi = [0, 0, 1, 2, 0]

텍스트:  A B A B C A B A B D
패턴:    A B A B D
                 ↑ 불일치! (j=4)

pi[3] = 2이므로, 패턴의 인덱스 2부터 비교 재개
→ 이미 "AB"가 매칭되었다는 정보를 활용

텍스트:  A B A B C A B A B D
패턴:            A B A B D
                     ↑ j=2부터 시작

// 실패 함수(pi 배열) 구성 — O(M)
private int[] buildFailureFunction(String pattern) {
    int m = pattern.length();
    int[] pi = new int[m];
    int len = 0; // 이전까지 일치한 접두사/접미사 길이
    int i = 1;

    while (i < m) {
        if (pattern.charAt(i) == pattern.charAt(len)) {
            len++;
            pi[i] = len;
            i++;
        } else {
            if (len > 0) {
                len = pi[len - 1]; // 이전 실패 함수 값으로 점프
            } else {
                pi[i] = 0;
                i++;
            }
        }
    }
    return pi;
}

public List<Integer> kmpSearch(String text, String pattern) {
    List<Integer> result = new ArrayList<>();
    int n = text.length(), m = pattern.length();
    int[] pi = buildFailureFunction(pattern);

    int i = 0; // 텍스트 포인터
    int j = 0; // 패턴 포인터

    while (i < n) {
        if (text.charAt(i) == pattern.charAt(j)) {
            i++;
            j++;
        }

        if (j == m) {
            result.add(i - j); // 매칭 위치 기록
            j = pi[j - 1];    // 다음 매칭을 위해 점프
        } else if (i < n && text.charAt(i) != pattern.charAt(j)) {
            if (j > 0) {
                j = pi[j - 1]; // 실패 함수 활용
            } else {
                i++;
            }
        }
    }
    return result;
}

// Java 내부 — 실제로는 네이티브 메서드로 최적화
public int indexOf(String str) {
    // OpenJDK: 기본적으로 단순 비교
    // 하지만 JIT 컴파일러가 SIMD 명령어로 최적화할 수 있음
}