문제 51
문자열 찾기
문자열 $T$와 길이가 $L$인 $Q$개의 문자열이 주어진다.
각 문자열이 $T$의 부분 문자열로 등장하는지 판별하라.
입력
첫 번째 줄에 문자열 $T$가 주어진다. $(1 \le \lvert T \rvert \le 10^6)$
두 번째 줄에 두 정수 $L$, $Q$가 공백으로 구분되어 주어진다. $(1 \le L \le \lvert T \rvert; 1 \le Q \le 200\,000; L \times Q \le 2 \cdot 10^6)$
세 번째 줄부터 $Q$개의 줄에 걸쳐 문자열 $P$가 하나씩 주어진다. $(\lvert P \rvert=L)$
모든 문자열은 알파벳 소문자로 이루어져 있다.
출력
각 쿼리마다 문자열 $P$가 $T$의 부분 문자열로 등장하면 Yes를, 그렇지 않다면 No를 한 줄에 하나씩 출력한다.
예제 입력 1
abracadabra 4 5 abra cada dabr acad abac
예제 출력 1
Yes Yes Yes Yes No
예제 입력 2
aaaaa 3 3 aaa aab baa
예제 출력 2
Yes No No
공식 해설
질의 문자열들을 하나의 자동자로 묶기
질의는 서로 독립적이므로 모두 읽어 둔 뒤 함께 처리할 수 있다. 각 문자열마다 본문을 다시 찾는 대신, 질의 문자열들을 Trie에 넣고 Aho–Corasick 자동자를 만든다. 질의마다 자신의 마지막 노드 번호를 저장한다. 같은 문자열은 같은 노드를 사용하면 된다.
자동자의 상태는 지금까지 읽은 본문의 접미사 중 Trie에 있는 가장 긴 문자열이다. 다음 문자로 내려갈 간선이 없으면, 현재 문자열의 더 짧은 접미사로 연결하는 실패 링크를 따라간다. 실패 링크와 빈 문자 전이를 BFS 순으로 채워 두면 문자 하나를 읽을 때 상수 시간에 다음 상태를 구할 수 있다.
길이가 모두 같다는 조건 이용하기
모든 질의의 길이는 $L$이고 Trie의 최대 깊이도 $L$이다. 본문의 어떤 위치에서 길이 $L$인 질의가 끝났다면 그 질의가 현재 가능한 가장 긴 접미사이므로 자동자는 반드시 해당 마지막 노드에 있다.
반대로 자동자가 질의의 마지막 노드에 도착했다면 그 질의가 방금 읽은 본문의 접미사로 등장한 것이다. 실패 링크가 가리키는 더 짧은 노드는 깊이가 $L$ 미만이라 다른 질의의 끝일 수 없다. 따라서 매번 실패 링크를 따라 모든 일치를 열거할 필요도 없다.
본문을 한 번 순회하며 도착한 노드들을 표시한다. 이후 각 질의의 마지막 노드가 표시되어 있으면 Yes, 아니면 No를 입력 순서대로 출력한다. 해시값을 비교하지 않으므로 충돌을 고려할 필요가 없다.
$n=\lvert T\rvert$, Trie의 노드 수를 $V$라 하면 시간복잡도는 $O(n+QL+26V+Q)$, 공간복잡도는 $O(n+26V+Q)$이다. $V\le QL+1$이고 알파벳 크기 $26$은 고정되어 있다.
구현 · 언어별 풀이
C++ 구현
노드의 문자 전이를 array<int, 26>으로 저장하고 실패 링크는 vector<int>로 관리한다. 노드 수의 상한 $QL+1$을 이용해 필요한 용량을 미리 확보하면 재할당 비용을 줄일 수 있다. 질의별 마지막 노드만 기억하면 되며, 길이가 모두 같으므로 검출 여부를 실패 링크로 다시 전파할 필요가 없다.
C 구현
전이표는 평탄 int 배열에 노드당 26칸을 둔다. 노드 수 상한은 입력 패턴 길이 합+1이다. BFS로 실패 링크와 전이를 채우고 각 패턴의 끝 노드를 저장한다. 동일한 길이이므로 긴 패턴의 suffix 끝 표식을 전파할 필요는 없다.
Python 구현
패턴 총길이가 2000000까지라 노드별 26개짜리 Python 리스트는 비싸다. 전이는 array('i')로 평탄화하고 fail·끝 노드도 정수 배열, 방문 여부는 bytearray로 둘 수 있다. 같은 패턴의 질의는 같은 끝 노드를 참조한다.
Java 구현
26*노드수 크기의 평탄 int[] 전이표와 int[] fail을 사용한다. 노드마다 객체·int[26]을 만드는 비용을 줄인다. 패턴 길이가 모두 같으므로 텍스트에서 도달한 끝 노드의 방문 여부로 각 질의를 답한다.
Rust 구현
전이는 Vec<[u32;26]>, 실패 링크와 끝 노드는 u32로 저장하면 usize 전이보다 메모리가 적다. 실제 Vec 접근에서만 usize로 바꾼다. 같은 길이의 패턴 끝 노드 방문 여부를 기록한다.
JavaScript 구현
모든 패턴의 길이가 같다는 성질을 이용한다. 트라이의 전이는 next[v * 26 + c] 형태의 평평한 Int32Array에 두고, 각 입력 패턴의 끝 정점 번호를 별도로 기록한다. 같은 패턴이 여러 번 나오면 같은 끝 정점에 연결되지만 질의 순서는 보존한다.
루트 번호는 $0$, 새 정점 번호는 $1$부터 사용한다. 만들지 않은 전이의 $0$과 루트로 돌아가는 완성 전이를 구분해야 하므로, 실패 링크를 만들기 전에 트라이 삽입을 모두 끝낸다. BFS 큐도 정점 번호 배열과 앞·뒤 인덱스로 구현해 shift()를 피한다.
본문을 읽으며 도달한 정점만 방문 표시하면 된다. 모든 패턴 길이가 $L$이므로 길이가 더 짧은 실패 링크 정점에 질의 패턴이 따로 끝날 수 없다. 일반적인 가변 길이 패턴 문제처럼 실패 링크 전체에 등장 횟수를 전파할 필요는 없다.
정점 수의 상한은 $1+LQ$이다. 전이 배열은 정점당 $26$개의 $4$바이트 정수를 사용해 최대 약 $208$MB이며, 정점마다 JS 객체와 Map을 만드는 것보다 메모리 사용을 예측하기 쉽다. 문자 입력 전체를 여러 토큰 배열로 복제하지 않고 패턴별로 삽입한다.