백준 1786 (찾기)

www.acmicpc.net/problem/1786

1786번: 찾기

 

문제가 길어서 링크를 넣는다.

이 문제에서 풀이 방식을 설명하고 있다.

풀이는 KMP 알고리즘을 이용하면 된다.

 

KMP 알고리즘은 빠르게 같은 문자를 찾는 방식이다.

 

접두사로 접미사에 얼마나 연속적으로 나오는가를 이용하는 알고리즘이다 시간복잡도가 O(n) 에 가깝기 때문에 많이 사용 되고 있다.

 

bowbowbow.tistory.com/6

KMP : 문자열 검색 알고리즘

 

자세한 구동방식은 이블로그에 정말 잘 정리되어 있다.

 

KMP 알고리즘 코드의 핵심은

while(j > 0 && T.charAt(i) != P.charAt(j)) {
	j = table[j - 1];
}

이 부분이다. 

table 배열은 이미 접두사가 접미사에 얼마나 반복이 되는지 저장을 해두었다.

while 문을 통해 겹치지 않는 부분까지 중간과정을 건너 뛰게 된다.

 

KMP 알고리즘의 핵심은 비교문자와 찾고자하는 문자가 어디까지 같은 문자였는지를 이용하는 방식이다.

 

<전체코드>

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;

import javax.management.Query;

import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

public class Main {

	static StringBuilder sb = new StringBuilder();
	
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        
        String T = bufferedReader.readLine();
        String P = bufferedReader.readLine();
        
        int lenT = T.length();
        int lenP = P.length();
        
        int[] table = new int[lenP];
        
        int j = 0;
        for(int i = 1; i < lenP ; i++) {
        	while(j > 0 && P.charAt(i) != P.charAt(j)) {
        		j = table[j - 1];
        	}
        	
        	if(P.charAt(i) == P.charAt(j)) {
        		table[i] = ++j;
        	}
        }
        
        int count = 0;
        
        j = 0;
        
        for(int i = 0 ; i < lenT; i++) {
        	while(j > 0 && T.charAt(i) != P.charAt(j)) {
        		j = table[j - 1];
        	}
        	
        	if(T.charAt(i) == P.charAt(j)) {
        		if(j == lenP - 1) {
        			count++;
        			sb.append((i - j + 1) + " ");
        			j = table[j];
        		}
        		else {
        			j++;
        		}
        	}
        }
        
        System.out.println(count+ "\n" + sb);
    }
        
}