문제
텍스트 문자열 T에서 패턴 문자열 P가 등장하는 횟수와 각 시작 위치(1-indexed)를 모두 출력하는 문제다. 단순 비교(Brute Force)는 O(|T|×|P|)이므로 T와 P가 길 경우 시간 초과가 발생한다. KMP(Knuth-Morris-Pratt) 알고리즘을 적용하면 실패 함수(failure function, pi 배열)를 이용해 불필요한 비교를 건너뜀으로써 O(|T|+|P|)에 해결할 수 있다.
입력
- 첫째 줄: 텍스트 문자열 T (공백 포함 가능)
- 둘째 줄: 패턴 문자열 P (공백 포함 가능)
출력
- 첫째 줄: 패턴이 등장하는 횟수
- 둘째 줄: 각 시작 위치를 공백으로 구분하여 출력 (1-indexed)
예제
| 입력 | 출력 |
|---|---|
ABABABABABAB ABAB | 4 1 3 5 7 |
풀이
KMP 알고리즘을 두 단계로 나누어 구현한다. 먼저 실패 함수(pi 배열)를 계산하고, 이를 이용해 텍스트에서 패턴을 탐색한다.
getPi(P): 패턴의 접두사이자 접미사인 최대 길이 배열pi계산 (O(|P|))- KMP 탐색: 텍스트 인덱스 i를 앞에서 뒤로 이동, 패턴 인덱스 j를 유지
- 불일치 발생 시
j = pi[j-1]로 되돌아가 이전 일치 정보를 재활용 j+1 == |P|이면 패턴 발견 → 시작 위치i - |P| + 2를 기록하고j = pi[j]로 이동
핵심 아이디어: pi 배열을 통해 이미 일치한 접두사 정보를 저장함으로써, 불일치 시 처음부터 다시 비교하지 않고 직전 일치 접두사 길이만큼만 되돌아간다.
코드
package com.ssafy.an.day149;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
public class Day126BOJ1786문자열 { // 1786 찾기
static int N, M;
static int[] pi;
static String str, ptn;
static List<Integer> list;
public static void main(String args[]) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
str = br.readLine();
ptn = br.readLine();
list = new ArrayList<Integer>();
pi = getPi(ptn);
kmp();
for (int ele : list)
sb.append(ele).append(" ");
System.out.println(list.size());
System.out.println(sb.toString());
br.close();
}
static void kmp() {
int j = 0;
N = str.length();
M = ptn.length();
for (int i = 0; i < N; i++) {
while (j > 0 && str.charAt(i) != ptn.charAt(j))
j = pi[j - 1];
if (str.charAt(i) == ptn.charAt(j)) {
if (j + 1 == M) {
list.add(i - M + 2);
j = pi[j];
} 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 = pi[j - 1];
if (str.charAt(j) == str.charAt(i))
pi[i] = ++j;
}
return pi;
}
}복잡도
- 시간: O(|T| + |P|) — pi 배열 생성 O(|P|) + KMP 탐색 O(|T|)
- 공간: O(|P|) — pi 배열 및 결과 리스트