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

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

16916번: 부분 문자열

1. 주의할 점

- KMP 알고리즘에 대해 알고 있어햐 한다

 

2. 구현

- 문자열 P와 S를 입력 받는다

- getPi()함수를 통해 접미사와 접두사의 일치 길이를 나타내는 배열을 반환한다

- KMP 알고리즘을 통하여 진행한다

- KMP 알고리즘에 대해 간략히 설명을 하면 다음과 같다

Origin의 문자열은 i를 통해 문자를 가리키고, Pattern의 문자열은 j를 통해 문자를 가리킨다

Origin[i] == Pattern[j]이면 i와 j모두 1씩 더한다

일치하지 않고 j 가 0이 아니라면, j = pi[j-1]을 통해 그 이전의 문자로 돌아간다(직전 문자에서 접미사와 접두사가 일치했던 부분까지)

일치하지 않고 j가 0이라면 i만 1을 더한다

 

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

public class Main_bj_16916_부분문자열 {

	static int ans=0;
	static int[] getPi(String pattern) {
		int[] pi = new int[pattern.length()];
		int j=0;
		for(int i=1;i<pattern.length();i++) {
			while(j>0 && pattern.charAt(i)!=pattern.charAt(j)) {
				j = pi[j-1];
			}
			if(pattern.charAt(i)==pattern.charAt(j)) 
				pi[i] = ++j;
		}
		return pi;
	}
	
	static void KMP(String origin, String ptn) {
		int[] pi = getPi(ptn);
		int j=0;
		for(int i=0;i<origin.length();i++) {
			while(j>0 && origin.charAt(i)!=ptn.charAt(j)) {
				j=pi[j-1];
			}
			if(origin.charAt(i)==ptn.charAt(j)) {
				if(j==ptn.length()-1) {
					ans=1;
					break;
				}
				else
					j++;
			}
		}
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String origin = br.readLine();
		String pattern = br.readLine();
		KMP(origin,pattern);
		System.out.println(ans);
	}
}