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

---

 

• 코드

실패 코드1 :  contains를 통해 포함이 되는지 안되는지 판별 후 포함되면 1, 포함되지않으면 0 출력 => 시간초과

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub        
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String firstInput = br.readLine();
		String secondInput = br.readLine();
		
		if(firstInput.contains(secondInput))
			System.out.println(1);
		else
			System.out.println(0);
    }
}

 

 

실패 코드2 : firstInput 배열에서 secondInput의 length index만큼부터 시작해서 같으면 그전이 다맞나 체크함. => 시간초과

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub        
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String a = br.readLine();
		char[] firstInput = a.toCharArray();
		String b = br.readLine();
		char[] secondInput = b.toCharArray();
		
		boolean check = false;
		for(int i=secondInput.length-1;i<firstInput.length;i++) {
			if(check)
				break;
			if(firstInput[i] == secondInput[secondInput.length-1]) {
				int index = secondInput.length-1;
				check = true;
				for(int j = i; j>i-secondInput.length;j--) {
					if(firstInput[j]!=secondInput[index--]) {
						check = false;
						break;
					}
				}
			}
		}
		
		if(check)
			System.out.print(1);
		else
			System.out.print(0);
    }
}

 

성공 코드 : KMP 알고리즘을 공부한 뒤 KMP 알고리즘으로 풀어보았다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {	
	static String firstString, secondString;
	static int pi[];
	
	public static void main(String[] args) throws IOException { 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		firstString = br.readLine();
		secondString = br.readLine();
		pi = new int[secondString.length()];
				
		System.out.println(KMP());
	}

	// KMP 알고리즘 - pi[] 배열에서 주어진 문자열의 인덱스 0부터 i까지의 부분 문자열 중
	// 접두사 == 접미사가 되는 가장 긴 접두사의 길이를 넣는다.
	// 현재 밑 코드에서 접두사는 j(왼쪽), 접미사는 i(오른쪽)이다.
	static int KMP() {
		// j 접두사
		int j = 0;
		
		// i 접미사
	    for (int i = 1; i < secondString.length(); ++i) {
	        while (j > 0 && secondString.charAt(i) != secondString.charAt(j)) j = pi[j - 1];
	        if (secondString.charAt(i) == secondString.charAt(j)) pi[i] = ++j;
	    }
	    
	    j = 0;
	    for (int i = 0; i < firstString.length(); ++i) {
	        while (j > 0 && firstString.charAt(i) != secondString.charAt(j)) j = pi[j - 1];
	        if (firstString.charAt(i) == secondString.charAt(j)) {
	            if (j == secondString.length() - 1) {
	                return 1;
	            }
	            else ++j;
	        }
	    }
	    return 0;
	}
}