백준_16916 부분 문자열(자바) / 문자열(KMP)

시간&메모리 제한

 

문제

 

입력&출력

 

문제

package com.Back;

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

public class Back_16916 {
	static String S;
	static String P;
	static int ans;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		S = br.readLine();
		P = br.readLine();
		KMP();
		System.out.println(ans);
	}

	private static void KMP() {
		int [] pi = getPi();
		int j = 0;
		for (int i = 0; i < S.length(); i++) {
			while(j>0 && S.charAt(i)!=P.charAt(j)) {
				j=pi[j-1];
			}
			if(S.charAt(i)==P.charAt(j)) {
				if(j==P.length()-1) {
					ans=1;
					break;
				}else {
					j++;
				}
			}
		}
	}

	private static int[] getPi() {
		int[] pi = new int[P.length()];
		int j = 0;
		for (int i = 1; i < P.length(); i++) {
			while(j>0 && P.charAt(i)!=P.charAt(j)) {
				j = pi[j-1];
			}
			if(P.charAt(i)==P.charAt(j)) {
				pi[i]=++j;
			}
		}
		return pi;
	}
}

// 틀린 풀이
//public class Back_16916 {
//
//	public static void main(String[] args) throws IOException {
//		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		String S = br.readLine();
//		String P = br.readLine();
//		StringBuilder sb = new StringBuilder(P);
//		int ans = 0;
//		for (int i = 0; i <= S.length()-P.length(); i++) {
//			if(S.substring(i, i+P.length()).equals(sb.toString())) {
//				ans = 1;
//				break;
//			}
//		}
//		System.out.println(ans);
//	}
//}

 

※ 내 생각

이 문제는 문자열을 이용해서 해결하는 문제입니다.

for문을 돌려서 하나하나 찾는 방법으로 해결하면 시간초과가 발생합니다.
시간 초과 해결하기 위해서 효율적인 검색 알고리즘을 구현할 필요가 있었습니다.

바로 KMP의 사용입니다.
접두사와 접미사를 이용해서 찾습니다.

접두사와 접미사가 동일한 범위가 될때까지 찾아줍니다.
그리고 접두사 부터 비교 했는데 틀리면 바로 접미사 위치에서 찾을 수 있습니다.
중간을 다 찾아보는 문제가 발생하지 않습니다.