문제 53
접두사 사전
처음에는 등록된 단어가 없다.
$Q$개의 쿼리를 순서대로 처리하라.
쿼리는 다음 중 하나이다.
1 S: 단어 $S$를 등록한다.2 P: 지금까지 등록한 단어 중 문자열 $P$로 시작하는 단어의 개수를 출력한다.
같은 단어를 여러 번 등록할 수 있으며 각각을 별개의 단어로 센다.
입력
첫 번째 줄에 정수 $Q$가 주어진다. $(1 \le Q \le 200\,000)$
두 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 하나씩 주어진다.
모든 문자열은 알파벳 소문자로 이루어져 있다. 입력으로 주어지는 모든 문자열의 길이의 합은 $10^6$ 이하이다.
출력
2 P 쿼리마다 지금까지 등록한 단어 중 문자열 $P$로 시작하는 단어의 개수를 한 줄에 하나씩 출력한다.
예제 입력 1
9 1 apple 1 app 2 app 1 apply 1 banana 2 a 2 apple 2 ban 2 cat
예제 출력 1
2 3 1 1 0
예제 입력 2
6 1 abc 1 abc 1 ab 2 abc 2 ab 2 a
예제 출력 2
2 3 3
공식 해설
같은 접두사를 가진 단어들을 Trie의 같은 경로에 저장한다. 각 노드에는 그 노드가 나타내는 접두사로 시작하는 등록 단어 수를 함께 저장한다.
단어 $S$를 등록할 때 앞에서부터 문자를 따라 내려가며 없는 노드를 만든다. 지나간 각 노드의 개수를 $1$ 늘린다. 같은 단어를 다시 등록해도 별개의 등록이므로 매번 개수를 늘린다.
질의 $P$에서는 그 문자들을 따라 내려간다. 경로가 중간에 없으면 $P$로 시작하는 단어가 없으므로 $0$이다. 끝까지 도착했다면 그 노드의 개수가 답이다. 단어가 $P$와 정확히 같은 경우도 이 노드를 지나므로 포함된다.
입력 문자열 길이의 합을 $L$이라 하면 각 문자를 상수 번 처리하므로 시간복잡도는 $O(L)$이다. 알파벳 크기가 $26$으로 고정되어 있어 공간복잡도도 $O(L)$이다.
구현 · 언어별 풀이
C++ 구현
각 노드는 $26$개의 자식 인덱스와 접두사 개수를 갖는 구조체로 표현할 수 있다. 새 노드의 자식은 모두 없음으로 초기화한다. 문자열 삽입 때만 노드를 만들고, 조회 도중 없는 간선을 만나면 $0$을 출력한다. 같은 단어의 재삽입도 지나간 노드들의 개수를 늘린다.
C 구현
노드당 26개의 자식 인덱스와 접두사 count를 배열에 둔다. 삽입할 때 지나간 각 노드의 count를 올리고 질의에서는 노드를 새로 만들지 않는다. 중복 삽입도 count에 반영한다.
Python 구현
총 문자열 길이가 백만이므로 전이는 평탄 array('i'), count는 정수 배열로 두면 객체 비용을 줄일 수 있다. 조회는 기존 노드만 따라가고 없는 자식이면 0이다. 중복 문자열도 삽입 횟수만큼 센다.
Java 구현
평탄 int[] child와 int[] count로 트라이를 구현한다. 자식 0을 부재 표시로 쓰면 실제 새 노드는 1부터 배정한다. 조회 도중 부재 자식을 발견하면 즉시 0을 반환한다.
Rust 구현
Vec<[u32;26]>와 Vec<u32> count를 사용한다. 부모의 자식 인덱스를 읽거나 갱신하는 borrow를 끝낸 뒤 새 노드를 push한다. 조회는 구조를 수정하지 않으며 같은 문자열의 중복 삽입도 센다.
JavaScript 구현
소문자 $26$개 전이를 평평한 Int32Array에 저장하고, 각 정점에는 그 접두사로 시작하는 삽입 문자열 수를 둔다. 정점 $0$을 루트로 사용하고 새 정점은 $1$부터 만든다. 총 문자열 길이가 백만 이하이므로 정점 수는 백만에 루트 하나를 더한 수를 넘지 않는다.
삽입할 때 방문한 각 접두사 정점의 개수를 $1$ 늘린다. 같은 문자열의 중복 삽입도 각각 세어야 하므로 Set으로 중복을 제거하지 않는다. 조회에서는 없는 전이를 만나면 $0$을 답하고 새 정점을 만들지 않는다.
이 문제는 접두사 개수만 묻기 때문에 별도의 문자열 전체 저장이나 말단 여부는 필요 없다. 개수는 $Q$ 이하라 $32$비트 배열에 들어간다. 각 문자를 한 번씩 처리해 전체 시간은 입력 문자열 길이의 합에 비례한다.