백준 1786 - 찾기

문제

https://www.acmicpc.net/problem/1786

문자열 T내에서 문자열 P 가 몇 번 등장하는 지 빈도와 등장 위치(인덱스)를 구하는
문제이다. 두 가지 접근을 통해 최적의 방식을 알아보자.

그리디한 방식의 문제

그리디하게 T내의 모든 위치에서 P와의 비교를 수행하면 T의 길이를 $N$, P의
길이를 $M$으로 가정했을 때, $O(NM)$의 시간복잡도로 수렴하게 된다.

static List<Integer> bruteForceSearch(String pattern, String target) {
    int n = target.length();
    int m = pattern.length();
    List<Integer> result = new ArrayList<>();

    for (int i = 0; i <= n - m; i++) {  // O(N)
        int j;
        for (j = 0; j < m; j++) {  // O(M)
            if (target.charAt(i + j) != pattern.charAt(j)) {
                break;  // 불일치하면 내부 루프 탈출
            }
        }
        if (j == m) { // 패턴을 찾은 경우
            result.add(i + 1);  // 1-based index 저장
        }
    }

    return result;
}

문제에서 주어질 수 있는 문자열의 최대 길이가 100만($10^6$)이므로 위 접근법은 최악의 경우
$10^6 \times 10^6 = 10^{12}$, 약 1조 횟수의 연산을 수행하게 된다. 이는 주어진 2초의 시간 조건을 충족하지 못한다.

About KMP

KMP 알고리즘은 임의의 문자열 내에서 특정 문자열(패턴)을 탐색할 때 유용한 알고리즘이다.
그리디한 방식과 비교해 $O(N + M)$의 시간 복잡도 내에 수행될 수 있어 훨씬 효율적이다.

LPS(Longest Prefix Suffix) 배열

KMP 알고리즘은 패턴 문자열 내부에서 반복되는 접두사/접미사 정보를 저장하는 것으로
시작된다. 해당 정보를 바탕으로 타겟 문자열 내에서 패턴을 검색할 때 비교 문자간 불일치가
발생하는 경우, 직전 비교 위치로 이동해 수행 시간을 단축한다. (이미 일치한 부분중 접두사와 겹치는 부분으로 이동해 비교 계속 진행)
lps[i]의 값은 패턴 문자열 pattern[0]부터 pattern[i]까지 접두사 == 접미사가 되는 가장 긴 부분 문자열 길이를 의미한다.

LPS 배열의 생성 과정은 다음과 같이 진행된다.

위 과정을 구현한 LPS 배열 생성 코드는 다음과 같다.

static int[] generateLps(String pattern) {
    int[] lps = new int[pattern.length()];

    int len = 0;
    int i = 1;
    while (i < pattern.length()) {
        if (pattern.charAt(i) == pattern.charAt(len)) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }

    return lps;
}

KMP 진행

• 탐색할 문자열과 패턴 문자열을 한 글자씩 비교하며 진행한다.
• 불일치 발생 시 lps[j - 1]을 참고하여 j를 이동한다.(처음부터 재탐색 x)
• 패턴과 완전히 일치하면(j == pattern.length()) 일치하는 위치를 저장하고,
  j를 lps[j - 1]로 설정하여 계속 진행한다.
• 모든 검색이 끝날 때까지(i == target.length()) 반복한다.

KMP 진행 과정은 아래 그림과 같이 진행된다.

풀이

앞서 설명한 KMP 알고리즘을 활용해 풀이하였다.
KMP를 진행하며 패턴 완벽히 일치할 때마다 i - target.length() + 1의 위치를
List<Integer>에 저장하면 리스트의 사이즈 = 발견된 패턴 개수, 리스트 요소 = 발견된 패턴 문자열 위치가 된다.
로직의 시간 복잡도는 KMP의 $O(N + M)$으로 수렴하고, $N=M=10^6$인 최악의 경우에도
무난히 시간 제한 2초를 통과한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String target = br.readLine();
        String pattern = br.readLine();

        List<Integer> result = kmp(pattern, target);
        System.out.println(result.size());
        System.out.println(result.stream().map(String::valueOf).collect(Collectors.joining(" ")));
        br.close();
    }

    static int[] generateLps(String pattern) {
        int[] lps = new int[pattern.length()];

        int len = 0;
        int i = 1;
        while (i < pattern.length()) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }

        return lps;
    }

    static List<Integer> kmp(String pattern, String target) {
        int n = target.length();
        int m = pattern.length();

        List<Integer> result = new ArrayList<>();
        int[] lps = generateLps(pattern);

        int i = 0, j = 0;
        while (i < n) {
            if (target.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            }

            if (j == m) {
                result.add(i - m + 1);
                j = lps[j - 1];
            } else if (i < n && target.charAt(i) != pattern.charAt(j)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }

        return result;
    }
}

결과