백준 16916 (부분 문자열)

문제

---

문자열 S의 부분 문자열이란, 문자열의 연속된 일부를 의미한다.

예를 들어, "aek", "joo", "ekj"는 "baekjoon"의 부분 문자열이고, "bak", "p", "oone"는 부분 문자열이 아니다.

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

 

 

 

 

풀이

---

conpulake.tistory.com/58?category=853119

백준 1786 (찾기)

 

위의 문제와 동일하지만 다른점은 해당 문자열이 포함되어있는지를 파악하는 문제다.

 

KMP알고리즘에 대해 정확하게 파악하고 있는것이 좋겠다.

문자열에서 부분문자열을 사용할 때 자주 사용되는 것 같다.

 

위에서 pi 를 구하고 kmp 알고리즘을 행하는 것을 똑같이 사용하면 된다.

 

<전체코드>

import java.io.*;
import java.util.*;

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 P = bufferedReader.readLine();
		String S = bufferedReader.readLine();
		
		int j = 0;
		int[] table = new int[S.length()];
		for(int i = 1 ; i < S.length() ; i++) {
			while(j > 0 && S.charAt(i) != S.charAt(j)) {
				j = table[j - 1];
			}
			
			if(S.charAt(i) == S.charAt(j)) {
				table[i] = ++j;
			}
		}
		
		j = 0;
		boolean isTrue = false;
		for(int i = 0 ; i < P.length() ; i++) {
			
			while(j > 0 && P.charAt(i) != S.charAt(j)) {
				j = table[j - 1];
			}
			
			if(P.charAt(i) == S.charAt(j)) {
				j++;
			}
			
			if(j == S.length()) {
				isTrue = true;
				break;
			}
		}
		
		if(isTrue)
			sb.append(1);
		else
			sb.append(0);
		
		System.out.println(sb);
	}
}