백준 JAVA 16916번 부분 문자열

문제 링크: https://www.acmicpc.net/problem/16916

16916번: 부분 문자열

 

비교하는 문자열의 길이가 짧다면 반복문을 중첩시켜 구할 수 있겠지만, 두 문자열의 최대 길이가 100만이므로 시간초과가 날 것이다. 따라서 KMP 알고리즘을 사용해야 한다. 

 

해당 알고리즘은 접두사와 접미사를 활용하여 판별한다. 

 

import java.math.BigInteger;
import java.util.*;
import java.io.*;



public class Main {

    static int t;
    static int [] table;
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        String p = br.readLine();

        table = new int [p.length()];

        System.out.println(KMP(s,p));

    }

    public static int KMP(String s, String p){
        makeTable(p);
        int sLength=s.length();
        int pLength=p.length();

        int idx =0;

        for(int i=0; i<sLength; i++){
            while(idx>0 && s.charAt(i) != p.charAt(idx)){
                idx=table[idx-1];
            }
            if(s.charAt(i)==p.charAt(idx)){
                if(idx==pLength-1){
                    idx=table[idx];
                    return 1;
                }
                else{
                    idx+=1;
                }
            }
        }
        return 0;
    }

    public static void makeTable(String p){
        int n = p.length();

        int idx=0;

        for(int i=1; i<n; i++){
            while(idx>0 && p.charAt(i)!=p.charAt(idx)){
                idx= table[idx-1];
            }

            if(p.charAt(i)==p.charAt(idx)){
                idx++;
                table[i]=idx;
            }
        }
    }

}