문자열 패턴 매칭 알고리즘

Brute Force

처음부터 끝까지 전부 탐색

• M: 찾을 패턴의 길이, N: 전체 텍스트 길이

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

라빈-카프 알고리즘

해시 값 함수 이용

• 패턴의 해시 값과 본문 안에 있는 하위 문자열의 해시 값만을 비교

• 최악은 O(M * N)이지만, 평균적으로는 선형에 가까운 빠른 속도를 가짐

구현

• 찾을 패턴의 길이만큼만 해시하여 비교
→ 해시 생성 O(M) * (N - M + 1)

• 슬라이딩 윈도우
→

보이어-무어 알고리즘

• 오른쪽에서 왼쪽으로 비교

• 패턴에 오른쪽 끝에 있는 문자가 불일치하고, 이 문자가 패턴 내에 존재하지 않는 경우, 패턴의 길이만큼 스킵

• 최악은 O(M * N), 최선은 O(N / M), 평균적으로는

KMP(Knuth-Morris-Pratt)

• 보이어-무어와 다르게 앞에서 뒤로 비교

• 불일치가 발생한 문자열의 앞 부분에 어떤 문자가 있는지 미리 알고 있으므로, 불일치가 발생한 앞 부분에 대하여 다시 비교하지 않고 수행

• O(M + N)

문제

코드

package org.example.string;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;

public class KMP {
    private static StringBuilder sb = new StringBuilder();
    private static String T, P;

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        T = br.readLine();
        P = br.readLine();

        int count = 0;

        // 접두사이면서 접미사인 최대 문자열의 길이 배열 만들기
        int[] KMPTable = new int[P.length()];

        int j = 0;
        for (int i = 1; i < P.length(); i++) {
            // j가 1 이상이고(j가 0이고 문자가 다르면 다음으로 넘어가야 해서) 문자가 다르면
            while (j > 0 && P.charAt(i) != P.charAt(j)) {
                // 그 전까지 일치한 길이를 j로 설정
                j = KMPTable[j - 1];
            }

            // 문자가 같으면
            if (P.charAt(i) == P.charAt(j)) {
                KMPTable[i] = ++j;
            }
        }

        // 부분 일치 테이블 배열 만들기
        j = 0;

        for (int i = 0; i < T.length(); i++) {
            // 다를 때
            while (j > 0 && T.charAt(i) != P.charAt(j)) {
                j = KMPTable[j - 1];
            }

            // 같으면
            if (T.charAt(i) == P.charAt(j)) {
                if (j == P.length() - 1) {
                    count += 1;
                    sb.append(i - P.length() + 2).append(" ");
                    j = KMPTable[j];
                }
                // j를 늘린다.
                else {
                    j += 1;
                }
            }
        }

        System.out.println(count);
        System.out.println(sb);
    }
}