[BOJ] 찾기

[1786] 찾기

www.acmicpc.net/problem/1786

Solution

• KMP 알고리즘을 사용해 원본 문자열 t에서 패턴 p를 찾았을 때 count 증가, StringBuilder에 순서 저장으로 구현
• 단순하게 모든 문자열을 일일이 비교하는 방법을 사용했을 때의 시간 복잡도는 O(NM) 이지만, KMP 알고리즘을 사용하면 O(N+M)의 시간 복잡도를 보인다.

 

 

소스코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    static StringBuilder sb;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] t = br.readLine().toCharArray();
        char[] p = br.readLine().toCharArray();
 
        sb = new StringBuilder();
        System.out.println(kmp(t, p));
        System.out.println(sb.toString());
    }
 
    private static int kmp(char[] t, char[] p) {
        int[] pi = getPi(p);
        int n = t.length;
        int m = p.length;
        int j = 0;
        int count = 0;
 
        for (int i = 0; i < n; i++) {
            while (j > 0 && t[i] != p[j]) {
                j = pi[j - 1];
            }
            if (t[i] == p[j]) {
                if (j == m - 1) {
                    count++;
                    sb.append((i - m + 2) + " ");
                    j = pi[j];
                } else {
                    j++;
                }
            }
        }
        return count;
    }
 
    private static int[] getPi(char[] p) {
        int[] pi = new int[p.length];
        int m = p.length;
        int j = 0;
 
        for (int i = 1; i < m; i++) {
            while (j > 0 && p[i] != p[j]) {
                j = pi[j - 1];
            }
 
            if (p[i] == p[j]) {
                pi[i] = ++j;
            }
        }
        return pi;
    }
 
    private static int stoi(String s) {
        return Integer.parseInt(s);
    }
}