[백준] 16916번 : 부분 문자열(JAVA)

https://www.acmicpc.net/problem/16916

16916번: 부분 문자열

풀이

KMP와 문자열문제입니다.(KMP를 안다면 바로 풀 수 있는 문제)

 

먼저 getpi()함수를 통하여 맞추고자 하는 글자의 중복위치를 체크해줍니다.

KMP()함수를 통하여 처음 문자열과 두번째 문자열을 1글자씩 비교합니다.

비교하면서 같을 경우 위치(j)를 증가시켜주고 j가 0보다 크고 서로 다를경우 맞는 위치까지 내려가기 위해 while문으로 j를 줄여줍니다.

for문이 끝날때까지 없다면 0, j가 두번째 문자열의 길이 - 1이랑 같으면 1을 리턴해줍니다.

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 

		System.out.print(KMP(br.readLine(), br.readLine()));
	}
	
	public static int[] getpi(String s1) {
		int[] pi = new int[s1.length()];
		int j = 0;
		for(int i = 1; i < s1.length(); i++) {
			while(j > 0 && s1.charAt(i) != s1.charAt(j)) {
				j = pi[j - 1];
			}
			if(s1.charAt(i) == s1.charAt(j)) {
				pi[i] = j += 1;
			}
		}
		return pi;
	}
	
	public static int KMP(String s, String s1) {
		int[] pi = getpi(s1);
		int j = 0;
		for(int i = 0; i < s.length(); i++) {
			while(j > 0 && s.charAt(i) != s1.charAt(j)) {
				j = pi[j - 1];
			}
			if(s.charAt(i) == s1.charAt(j)) {
				if(j == s1.length() - 1) {
					return 1;
				}
				else {
					j++;
				}
			}
		}
		return 0;
	}
}