(JAVA) 백준 1786번 : 찾기 --- [KMP]

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

1786번: 찾기

 

안녕하세요.

 

 

이 문제는 문자열 검색 알고리즘인 KMP의 기본 문제로서

 

문제에도 노골적으로 O(전체 문자열 길이 + 찾으려는 문자열 길이) 의 시간복잡도로 문자열을 탐색하라고 나와있다.

 

 

KMP 알고리즘에 대해 알고싶으면 백준 1701번 문제 포스팅을 보고 와도 좋다.

https://maivve.tistory.com/203

(JAVA) 백준 1701번 : Cubeditor

 

요점만 말하면

 

 

  1)  찾으려는 문자열의 접두사와 접미사 길이를 담은 배열 pi

 

  2)  이 pi를 활용하여 전체 문자열에서 중복을 제거해가며 일치하는 문자열이 있는지 체크

 

  3)  문자열의 시작 위치 인덱스를 리스트에 담는다.

 

 

가 KMP 알고리즘이고, 이 문제 풀이의 핵심이다.

 

 

 

 

자세한 설명은 위에 포스팅에 담겨있어서 여기서는 따로 개념 설명은 담지 않겠습니다.

 

 

이상입니다.

감사합니다!

 

 

 

소스코드

---

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.ArrayList;
	import java.util.List;
	// 찾기 문제
	// 문자열 + KMP 알고리즘 (문자열 탐색)
	public class p1786 {
	static List<Integer> list;
	public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	String str = br.readLine();
	String pattern = br.readLine();
	list = new ArrayList<Integer>();
	StringBuilder sb = new StringBuilder();
	// Pi 배열 구하기 (찾으려는 문자열의 접두사와 접미사 체크)
	int[] pi = getPi(pattern);
	kmp(pi, str, pattern);
	// 정답 출력을 위해 결과데이터 가공 작업
	for(int ele : list) {
	sb.append(ele).append(" ");
	}
	System.out.println(list.size());
	System.out.println(sb.toString());
	}
	// KMP 알고리즘 사용하여 문자열 탐색하기
	static void kmp(int[] pi, String str, String pattern) {
	int j = 0;
	int strLen = str.length();
	int patternLen = pattern.length();
	for(int i = 0; i < strLen; i++) {
	while(j > 0 && str.charAt(i) != pattern.charAt(j)) { // 다르면 같았던 다음 접미사로 바로 건너뛰기
	j = pi[j - 1];
	}
	if(str.charAt(i) == pattern.charAt(j)) { // 인덱스가 같은 문자 두 개가 같다.
	if(j + 1 == patternLen) { // pattern 문자열 전부가 같다면
	list.add(i - patternLen + 2); // 전체 문자열 중 패턴 문자열과 같은 문자열의 시작 인덱스를 구해야 하므로(게다가 1부터 시작함)
	j = pi[j]; // 초기화를 시켜줘야 함. 자기 자신은 어차피 0이라 0으로 직접 설정해도 되긴 할듯
	}
	else { // 바로 다음번째 문자를 가지고 비교해야 하므로
	j++;
	}
	}
	}
	}
	static int[] getPi(String str) {
	int j = 0; // 접두사 시작 인덱스
	int n = str.length();
	int[] pi = new int[n];
	for(int i = 1; i < n; i++) { // 접미사 시작 인덱스
	while(j > 0 && str.charAt(j) != str.charAt(i)) { // j > 0 인 이유는 최소 두 글자부터 비교하는 것이 맞아
	j = pi[j - 1]; // 다르면 이전의 문자열에서 접두사 - 접미사 같은 최대 길로 이동시킨다.
	}
	if(str.charAt(j) == str.charAt(i)) { // 같으면
	pi[i] = ++j;
	}
	}
	return pi;
	}
	}

view raw p1786.java hosted with ❤ by GitHub