문제 61
금지된 문자열
금지된 문자열이 $N$개 있다. $Q$개의 쿼리를 순서대로 처리하라.
각 쿼리마다 문자열 $T$ 안에 금지된 문자열이 하나 이상 등장하는지 판별하라.
입력
첫 번째 줄에 정수 $N$이 주어진다. $(1 \le N \le 200\,000)$
두 번째 줄부터 $N$개의 줄에 걸쳐 금지된 문자열 $P_i$가 하나씩 주어진다. $(\sum_{i=1}^{N} \lvert P_i \rvert \le 500\,000)$
그다음 줄에 정수 $Q$가 주어진다. $(1 \le Q \le 200\,000)$
그다음 줄부터 $Q$개의 줄에 걸쳐 문자열 $T$가 하나씩 주어진다. 입력으로 주어지는 모든 $T$의 길이의 합은 $10^6$ 이하이다.
모든 문자열은 알파벳 소문자로 이루어져 있다.
출력
각 문자열 $T$마다 금지된 문자열이 하나 이상 등장하면 Yes를, 그렇지 않다면 No를 한 줄에 하나씩 출력한다.
예제 입력 1
4 he she his hers 5 ahishers hello abc shelter hero
예제 출력 1
Yes Yes No Yes Yes
공식 해설
여러 금지 문자열을 동시에 찾기
금지 문자열을 모두 Trie에 넣고 각 문자열의 마지막 노드를 표시한다. Aho–Corasick 자동자를 만들어 질의 문자열을 한 번만 읽으면서 모든 금지 문자열의 등장을 판정한다.
각 상태는 지금까지 읽은 문자열의 접미사 중 Trie에 있는 가장 긴 문자열을 나타낸다. 다음 문자로 내려갈 수 없다면 실패 링크를 따라 더 짧은 접미사를 시도한다. 실패 링크와 빈 문자 전이를 BFS 순서로 미리 채우면 문자 하나를 읽을 때 다음 상태를 바로 구할 수 있다.
실패 링크의 검출 여부도 물려받기
현재 노드가 금지 문자열의 마지막이 아니어도 그 접미사가 금지 문자열일 수 있다. 따라서 노드의 검출 표시를 자기 자신의 마지막 표시와 실패 링크 노드의 검출 표시의 논리합으로 둔다.
예를 들어 금지 문자열이 abc와 b라면 본문 ab에서도 b를 찾아야 한다. ab 노드가 문자열의 끝이 아니더라도 실패 링크로 가는 b가 금지 문자열이므로 검출된다. 실패 링크는 더 얕은 노드를 가리키므로 BFS 순서에서 이 표시를 전파할 수 있다.
각 질의는 루트에서 새로 시작하고, 읽는 동안 검출 표시가 있는 상태에 한 번이라도 도착하면 Yes이다. 끝까지 없다면 No이다.
패턴 길이의 합을 $P$, 질의 문자열 길이의 합을 $R$, Trie 노드 수를 $V$라 하면 시간복잡도는 $O(P+26V+R)$, 공간복잡도는 $O(26V)$이다. $V\le P+1$이다.
구현 · 언어별 풀이
C++ 구현
각 Trie 노드에 $26$개 전이, 실패 링크와 검출 여부를 저장하고 queue<int>로 BFS한다. 검출 여부는 자신의 마지막 표시와 실패 링크 노드의 표시를 논리합한다. 질의마다 상태를 루트로 초기화해야 서로 다른 문자열을 이어 붙인 일치를 잘못 세지 않는다.
C 구현
노드당 26칸의 전이 배열과 실패 링크 fail, 금지 표식 bad를 저장한다. BFS 순서대로 bad[v] |= bad[fail[v]]를 반영한다. 패턴 길이가 서로 다르므로 현재 노드의 직접 끝 표식만 보면 접미사인 짧은 금지 패턴을 놓친다.
Python 구현
전이표를 평탄 array('i')로, 금지 표식을 bytearray로 두면 메모리를 줄일 수 있다. BFS에서 실패 링크의 금지 표식도 전파한다. 각 질의 문자열은 상태를 루트로 다시 시작한다.
Java 구현
평탄 int[] 전이와 boolean[] 금지 표식 bad를 사용한다. BFS 순서대로 bad[v] |= bad[fail[v]]를 반영하여 실패 링크 끝의 짧은 금지 패턴도 확인한다. 질의마다 루트에서 다시 시작하고 금지 상태에 도달하면 해당 문자열의 판정을 끝낼 수 있다.
Rust 구현
전이는 Vec<[u32;26]>, fail은 u32, bad는 bool 배열로 둔다. 실패 링크 BFS에서 suffix 금지 표식을 전파한다. 질의마다 상태 0에서 시작해 이전 문자열과 이어 매칭하지 않는다.
JavaScript 구현
트라이 전이를 정점당 $26$칸의 평평한 Int32Array로 두고 실패 링크와 금지 여부를 각각 별도 배열에 저장한다. 총 패턴 길이가 $500\,000$ 이하라 전이 배열의 최대 크기는 약 $52$MB이다. BFS 큐는 정수 배열과 앞·뒤 인덱스를 사용한다.
실패 링크를 만든 BFS 순서대로 bad[v] ||= bad[fail[v]]를 반영한다. 현재 정점 자체가 어떤 패턴의 끝이 아니어도 더 짧은 접미사가 금지 패턴이면 검출되어야 한다. 모든 패턴 길이가 같았던 문제와 달리 이 전파를 생략할 수 없다.
각 조회 문자열은 루트에서 시작하며, 문자 코드를 $0$부터 $25$로 바꾸어 완성된 전이를 따라간다. 금지 상태를 한 번 만나면 그 문자열의 판단은 끝난다. 다른 조회는 다시 루트에서 시작하므로 상태를 이어 쓰지 않는다.