[백준]16916번 부분 문자열

16916번: 부분 문자열

문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 아닌지 알아보자

두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다

문제 해결하기

• 두 문자열의 길이가 최대 100만
• 만약 단순한 문자열 탐색을 한다면 O(100만 x 100만 ) 이 된다 → 불가능
• KMP 알고리즘을 사용하자 . → O(|S|) + O(|P|) 의 시간복잡도

package cote;
import java.io.*;
import java.lang.reflect.Array;
import java.lang.reflect.Type;
import java.util.*;

public class Main {
    public static int[] pi;
    public static String gs,gp;

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;

    public static void setting() throws IOException{
        gs = br.readLine();
        gp = br.readLine();

    }
    // pi[i] 를 세팅한다
    public static void setPi(String n){
        int m = n.length();
        int begin = 1,matched = 0;
        pi = new int[m];

        while(begin + matched < m ){
            if(n.charAt(begin+matched) == n.charAt(matched)){
                // 일치 하는 경우
                matched++;
                pi[begin+matched-1] = matched;
            }else{
                // 불일치 하는 경우
                if(matched == 0 ){
                   // 불일치 하더라도 begin은 옆으로 이동해야함
                   begin++;
                }else{
                    // matched - pi[matched-1] 만큼 이동해야함
                    begin += matched - pi[matched-1];
                    // 이미 pi[matched-1]만큼 일치한다는 것을 알고있음
                    matched = pi[matched-1];
                }
            }
        }

    }
    // s 에서 p가 부분 문자열인지 확인하는 메소드
    public static boolean findStr(String s, String p){
        // p가 s의 부분문자열인지 확인
        setPi(p);
        int n = s.length(),m = p.length();
        int begin = 0,matched = 0;
        while(begin <= n - m ){
            if(matched < m && s.charAt(begin+matched) == p.charAt(matched)){
                // 일치하는 경우
                matched++;
                // matched ++ -> 모든 글자가 겹치게 된건지 확인해야함.
                if(matched==m){
                    return true;
                }
            }else{
                if(matched == 0) begin++;
                else{
                    begin += matched - pi[matched-1];
                    matched = pi[matched-1];
                }
            }
        }
        return false;
    }

    public static void main(String[] args) throws IOException {
        setting();
        boolean ans = findStr(gs,gp);

        if(ans) System.out.println(1);
        else System.out.println(0);
    }
}