[백준 / Java] 1786번: 찾기 (플레5)

문제 풀이 날짜: 2023.10.04
포스트 작성일: 2023.10.04

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 1786번: 찾기 (플레5) 

 

키워드

문자열, KMP 알고리즘

 

풀이 접근법

• KMP의 기초 구현법을 묻는 문제이다.
• KMP는 문자열의 맨 앞쪽 → 뒷쪽으로 포인터를 옮겨가며 일치 여부를 비교한다.
  • 본문은 움직이지 않고, 패턴 문자열의 포인터만 이동한다. 이미 알고 있는 접두사나 접미사는 스킵(패턴 포인터 이동)하고 유의미한 비교만 할 수 있도록 만들어준다.
  • 부분 일치 테이블 pi[]를 정의하여 인덱스 점프에 활용한다. 패턴 문자열의 부분 문자열 중, 접미사와 접두사 패턴을 보이는 최대 길이를 저장한다.
  • 찾으려고 하는 패턴 문자열이 대칭성이 없다고 하더라도(패턴 문자열의 맨 앞으로 밀어버리더라도) 완전 탐색에 비해서는 유리하다.
• pi[] 배열에는 매칭이 실패했을 때, 패턴 포인터가 돌아갈 곳을 미리 계산해둔다.
  • i까지 맞았을 경우, 패턴 포인터를 위의 길이 만큼 앞쪽으로 당긴다. (j = pi[j])
  • 예를 들어, 패턴 문자열이 `abcdabc`라고 할 때, 접미사와 접두사 패턴을 보이는 것은 길이 3짜리 `abc`이다. 이것을 참고하여 패턴 포인터를 옮긴다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		char[] text = br.readLine().toCharArray();
		char[] pattern = br.readLine().toCharArray();
		
		int tLen = text.length;
		int pLen = pattern.length;
		
		//1. 패턴 문자열에 대해서 부분 일치 테이블 생성
		int[] pi = new int[pLen];
		for(int i = 1, j = 0; i < pLen; i++) { //i : 접미사 포인터 (1부터 시작)
			while(j > 0 && (pattern[i] != pattern[j])) {
				j = pi[j - 1]; //pi값을 따라 패턴 포인터 밀기
			}
			
			if(pattern[i] == pattern[j]) { pi[i] = ++j; } //대칭을 이룰 경우
			else pi[i] = 0; //대칭이 아닌 경우
		}
		
		int count = 0;
		List<Integer> list = new ArrayList<>();
		//i : 텍스트 포인터, j : 패턴 포인터
		for(int i = 0, j = 0; i < tLen; i++) {
			while(j > 0 && (text[i] != pattern[j])) {
				j = pi[j - 1]; //pi값을 따라 패턴 포인터 밀기
			}
			
			if(text[i] == pattern[j]) { //패턴과 원본 문자가 일치한다면
				if(j == pLen - 1) { //j가 패턴의 마지막 인덱스라면
					count++;
					list.add(i - j);
					j = pi[j]; //pi값을 따라 패턴 포인터 밀기
				}
				else { j++; } //패턴의 다음 문자 조사
			}
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append(count).append("\n");
		if(count > 0) {
			for(int i : list) {
				sb.append(i + 1).append(" ");
			}
		}
		
		System.out.print(sb);
	}

}

---

 

 

git 링크

(git 링크 첨부)