문제 50
패턴 찾기
문자열 $T$와 문자열 $P$가 주어진다.
$T$에서 $P$와 일치하는 부분 문자열이 시작하는 모든 위치를 구하라.
문자열의 첫 번째 문자의 위치는 $1$이다.
서로 겹치는 경우도 모두 포함한다.
입력
첫 번째 줄에 문자열 $T$가 주어진다. $(1 \le \lvert T \rvert \le 10^6)$
두 번째 줄에 문자열 $P$가 주어진다. $(1 \le \lvert P \rvert \le 10^6)$
두 문자열은 알파벳 소문자로 이루어져 있다.
출력
첫 번째 줄에 $T$에서 $P$가 등장하는 횟수를 출력한다.
$P$가 한 번 이상 등장한다면 두 번째 줄에 각 부분 문자열이 시작하는 위치를 오름차순으로 출력한다.
위치는 공백으로 구분한다.
예제 입력 1
ababa aba
예제 출력 1
2 1 3
예제 입력 2
abcdefgh ijk
예제 출력 2
0
공식 해설
본문과 패턴의 길이가 각각 $10^6$까지 커지므로 모든 시작점에서 패턴을 처음부터 비교하면 느리다. 앞에서 이미 맞춘 부분을 다음 비교에 재사용하자.
이미 맞춘 부분을 다시 비교하지 않기
패턴의 길이를 $m$이라 하자. KMP의 접두사 함수 $\pi_i$는 $P_0\cdots P_i$의 접두사이면서 접미사인 문자열 중 자기 자신을 제외한 최장 길이이다.
$\pi$를 구할 때 이전 일치 길이 $j$에서 다음 문자가 다르면 $j\leftarrow\pi_{j-1}$로 줄인다. 문자가 같아지면 $j$를 하나 늘린다. 실패할 때 가능한 다음 접두사 길이로 바로 돌아가므로 같은 부분을 처음부터 비교하지 않는다.
본문을 읽을 때도 현재까지 맞춘 패턴 길이 $j$를 유지한다. 다음 문자가 $P_j$와 다르면 같은 방식으로 돌아가고, 같으면 $j$를 늘린다. $j=m$이 되면 패턴을 하나 찾았다.
겹치는 등장도 이어서 찾기
본문의 $0$부터 센 위치 $i$에서 일치가 끝났다면 시작 위치는 문제의 $1$ 기반 인덱스로 $i-m+2$이다. 이를 기록한 뒤 $j=\pi_{m-1}$로 바꾸고 다음 문자를 읽는다.
일치 직후 $j$를 무조건 $0$으로 만들면 앞의 일치와 겹치는 부분을 놓칠 수 있다. 접두사와 접미사가 같은 최장 길이를 남기면 이미 읽은 문자를 다음 일치의 시작으로 재사용할 수 있다.
기록한 위치는 발견 순서대로 증가하므로 개수와 위치를 그대로 출력한다. 각 단계에서 $j$가 증가하는 횟수만큼만 다시 감소할 수 있어 시간복잡도는 $O(\lvert T\rvert+\lvert P\rvert)$이다. 입력과 발견 위치를 포함한 공간복잡도도 같은 차수이다.
구현 · 언어별 풀이
C++ 구현
본문과 패턴은 string, 접두사 함수와 발견 위치는 vector<int>로 저장한다. 일치 길이 $j$가 $0$일 때는 pi[j - 1]을 읽지 않는다. 패턴 전체가 맞으면 위치를 기록한 즉시 $j$를 마지막 접두사 함수 값으로 바꾸어 겹치는 등장도 찾는다.
C 구현
P의 int 접두사 배열을 만들고 T를 한 번 훑는다. 일치한 뒤 j=pi[j-1]로 돌아가 겹치는 일치도 찾는다. 출력 시작점은 1-based이므로 i-m+2이며 문자열 길이·인덱스 계산의 기준을 통일한다.
Python 구현
bytes와 접두사 리스트를 사용하면 ASCII 문자 비교를 직접 할 수 있다. 일치 뒤 접두사 길이로 돌아가므로 겹치는 출현도 남는다. 결과를 하나씩 print하지 말고 묶어서 출력한다.
Java 구현
String.charAt()과 int[] pi로 구현한다. 패턴 전체가 일치했을 때 다음 검사 전에 j를 pi[j-1]로 되돌린다. substring을 매 위치에서 만들지 않는다.
Rust 구현
as_bytes()와 Vec<usize> pi를 사용한다. j=0일 때 pi[j-1]을 읽지 않고, 일치 직후에도 실패 링크로 돌아간다. 출력 시작점만 1-based로 변환한다.
JavaScript 구현
두 줄을 따로 읽고 줄 끝의 개행만 제거한다. 입력이 소문자 ASCII이므로 p[i] 또는 charCodeAt(i)로 문자를 비교해도 된다. 실패 함수는 길이 $|P|$의 Int32Array에 저장한다.
일치를 찾은 뒤 j = pi[j - 1]로 돌아가면 겹치는 등장도 셀 수 있다. 다음 코드는 검색 중 현재 문자까지 읽은 뒤 패턴 전체가 일치했을 때의 처리이다.
if (j === p.length) {
positions.push(i - p.length + 2);
j = pi[j - 1];
}배열의 인덱스는 $0$부터 시작하지만 출력 위치는 $1$부터 시작하므로 위 보정이 필요하다. 최대 백만 개 위치를 줄마다 출력하지 말고 적당한 크기의 출력 버퍼로 묶어 내보낸다. 패턴이 본문보다 긴 경우에도 같은 순회에서 일치가 한 번도 생기지 않는다.