정범의 프로그래밍 블로그 입니다.

4 분 소요

1. 핵심 개념 및 근거

핵심 개념

  • 알고리즘: KMP 알고리즘
  • 자료 구조: 1차원 배열(부분 일치 테이블 pi 저장용)

선택 근거 및 제약 사항

  • 텍스트(T)의 길이가 최대 50만, 패턴(P)의 길이가 최대 10만입니다.
  • 단순 비교(Brute-force) 방식의 시간 복잡도는 $O(N \times M)$으로, 최악의 경우 500억 번의 연산이 필요하여 시간 초과가 발생합니다.
  • KMP 알고리즘은 이미 비교한 정보를 활용해 불필요한 비교를 건너뛰므로 $O(N + M)$의 시간 복잡도로 해결 가능합니다.


2. 추론 과정

  • 키워드: “단어가 몇 번 등장하는지”, “문자열 검색”.
    • 문자열 길이를 보는 순간, $O(N^2)$이나 $O(NM)$은 탈락입니다.
    • 선형 시간($O(N)$) 내에 문자열을 훑으며 패턴을 찾아야 함을 직감해야 합니다.


3. 설계 및 접근

  1. 부분 일치 테이블 만들기
    • 패턴 내에서 접두사와 접미사가 일치하는 최대 길이를 미리 계산하여 pi[] 배열에 저장합니다.
  2. 본문 검색
    • 텍스트를 한 글자씩 읽으며 패턴과 비교합니다.
    • 문자가 불일치할 경우, 부분 일치 테이블을 이용해 패턴의 비교 위치를 효율적으로 이동시킵니다.
    • 패턴이 완전히 일치하면 카운트를 증가시키고, 다시 부분 일치 테이블를 참조하여 다음 탐색을 이어갑니다.


4. 예시 시뮬레이션

  • Text: ababcababa, Pattern: aba
    1. pi 배열 생성: aba -> [0, 0, 1] (접두사 a와 접미사 a가 일치)
    2. ababc... 탐색:
    • aba 발견 (index 0~2): count = 1.
    • 불일치 발생 시 pi[2]를 참조해 다음 위치인 index 2부터 다시 비교 시작.
    • 이런 식으로 텍스트 전체를 한 번만 훑습니다.


5. 주의 사항

  • pi 배열의 인덱스 처리 (j = pi[j-1] 부분)에서 Out of Bounds 에러 주의.
  • 패턴을 찾은 직후, 다음 탐색 위치를 단순히 j=0으로 초기화하면 안 되고 j = pi[j-1]을 통해 중첩된 패턴도 찾아야 합니다 (예: aaaa에서 aa 찾기).
  • KMP 알고리즘을 사용할 때 접두사 i, 접미사 j로 사용한다면 오타 주의.


6. 코드 풀이

6.1 부분 일치 테이블 만들기

static int[] getPi(String pattern) {
        int m = pattern.length();
        int pi[] = new int[m];
        int j = 0;
 
        for (int i = 1; i < m; i++) {
            // 불일치 시 j를 이전의 일치했던 곳으로 되돌림
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = pi[j - 1];
            }
 
            // 일치하면 pi 배열에 그 길이를 기록하고 j 증가
            if (pattern.charAt(i) == pattern.charAt(j)) {
                pi[i] = ++j;
            }
        }
 
        return pi;
 
    } // getPi 종료
  • getPi 함수는 “패턴 안에서 접두사와 접미사가 일치하는 최대 길이”를 미리 계산하는 역할을 합니다.
  • 불일치할 때
    • pattern.charAt(i) != pattern.charAt(j)라면, j를 j = pi[j - 1]로 이동합니다.
    • 불일치가 일어났을 때, j-1까지는 이미 일치했다는 것을 알 수 있습니다.
    • 그 길이 만큼은 다시 검사하지 않았도 무조건 일치함이 보장됩니다.
  • 일치할 때
    • pattern.charAt(i) == pattern.charAt(j)라면, j를 하나 키우고 그 값을 pi[i]에 기록합니다.

6.2 KMP 알고리즘 메인 로직

static int kmp(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int[] pi = getPi(pattern); // 부분일치 테이블 가져오기
 
        int count = 0;
        int j = 0; // 패턴의 인덱스
 
        for (int i = 0; i < n; i++) {
 
            // 현재 문자가 불이치하면, pi 배열을 이용해 j 위치를 되돌림
            while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
                j = pi[j - 1];
            }
 
            // 문자가 일치하는 경우
            if (text.charAt(i) == pattern.charAt(j)) {
 
                // 패턴 전체가 일치한 경우
                if (j == m - 1) {
                    count++;
                    j = pi[j]; // 다음 매칭을 위해 j 이동
                } else {
                    j++;
                }
 
            }
 
        }
 
        return count;
 
    } // kmp 종료
  • kmp 함수는 앞서 getPi 함수를 통해 만든 부분 일치 테이블을 활용하여, 본문(Text)에서 패턴(Pattern)이 어디에 나타나는지 실제로 찾아내는 과정입니다.
  1. 불일치 발생 시
    • 본문의 문자와 패턴의 문자가 다르면(text.charAt(i) != pattern.charAt(j)), j 포인터를 pi 테이블의 정보에 따라 뒤로 점프시킵니다.
    • 이 과정은 문자가 일치하거나, j가 $0$이 될 때까지 반복됩니다.
  2. 일치할 때
    • 본문과 패턴의 문자가 같다면, 패턴의 다음 글자를 비교하기 위해 j를 1 증가시킵니다.
  3. 패턴을 완전히 찾았을 때
    • j가 패턴의 마지막 인덱스(m - 1)까지 도달했다면, 패턴 하나를 온전히 찾은 것입니다.
    • 여기서 j = pi[j]를 해주는 이유는, 찾은 패턴의 뒷부분이 다음 매칭되는 패턴의 앞부분과 겹칠 수 있기 때문입니다.

6.3 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Solution {
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
 
        int T = Integer.parseInt(br.readLine().trim());
 
        // tc 수행
        for (int tc = 1; tc <= T; tc++) {
 
            String text = br.readLine();
            String pattern = br.readLine();
            int result = kmp(text, pattern);
 
            // 출력 내용 추가
            sb.append("#" + tc + " " + result + "\n");
 
        } // tc 종료
 
        // 출력
        System.out.println(sb);
 
    } // main 종료
 
    // 부분일치 테이블 생성 함수
    // 패턴 내에서 접두사와 접미사가 일치하는 길이를 계산
    static int[] getPi(String pattern) {
        int m = pattern.length();
        int pi[] = new int[m];
        int j = 0;
 
        for (int i = 1; i < m; i++) {
            // 불일치 시 j를 이전의 일치했던 곳으로 되돌림
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = pi[j - 1];
            }
 
            // 일치하면 pi 배열에 그 길이를 기록하고 j 증가
            if (pattern.charAt(i) == pattern.charAt(j)) {
                pi[i] = ++j;
            }
        }
 
        return pi;
 
    } // getPi 종료
 
    // KMP 알고리즘 메인 로직
    static int kmp(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int[] pi = getPi(pattern); // 부분일치 테이블 가져오기
 
        int count = 0;
        int j = 0; // 패턴의 인덱스
 
        for (int i = 0; i < n; i++) {
 
            // 현재 문자가 불이치하면, pi 배열을 이용해 j 위치를 되돌림
            while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
                j = pi[j - 1];
            }
 
            // 문자가 일치하는 경우
            if (text.charAt(i) == pattern.charAt(j)) {
 
                // 패턴 전체가 일치한 경우
                if (j == m - 1) {
                    count++;
                    j = pi[j]; // 다음 매칭을 위해 j 이동
                } else {
                    j++;
                }
 
            }
 
        }
 
        return count;
 
    } // kmp 종료
 
}

카테고리:

업데이트:

참고