금칙어 등장 횟수
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
게시판 글 text와 금칙어 목록 words가 주어집니다. 각 금칙어가 글 안에 몇 번 나타나는지 세어, words와 같은 순서로 배열에 담아 반환하세요.
등장 위치가 겹쳐도 모두 셉니다. 예를 들어 "aaaa"에 "aa"는 시작 위치 0, 1, 2에서 세 번 나타납니다. words에 같은 단어가 여러 번 들어 있을 수 있으며, 각각 따로 답합니다.
입출력 예
| text | words | result |
|---|---|---|
"ababa" | ["aba", "ab", "b", "c"] | [2, 2, 2, 0] |
"aaaa" | ["a", "aa", "aaa", "aaaaa"] | [4, 3, 2, 0] |
"hershe" | ["he", "she", "hers", "her"] | [2, 1, 1, 1] |
입출력 예 설명
예 1 — "aba"는 위치 0과 2에서 겹쳐 나타납니다. "c"는 나타나지 않습니다.
예 2 — 겹치는 등장을 모두 셉니다. 글보다 긴 단어는 0번입니다.
예 3 — "he"는 위치 0과 4, "she"는 위치 3에서 나타납니다. 한 위치에서 여러 단어가 동시에 끝날 수도 있습니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(text: string, words: string[]) → int[]
제한 사항
-
text.length -
words.length,words[i].length - 모든 금칙어 길이의 합은 이하입니다.
text와words[i]는 영어 소문자로만 이루어져 있습니다.
기대 복잡도
- 시간
- O(|text| + sum|words| * 26)
- 공간
- O(sum|words| * 26)
입출력 예
| text | words | 기대 출력 |
|---|---|---|
"ababa" | ["aba","ab","b","c"] | [2,2,2,0] |
"aaaa" | ["a","aa","aaa","aaaaa"] | [4,3,2,0] |
"hershe" | ["he","she","hers","her"] | [2,1,1,1] |
힌트
힌트
단어마다 KMP를 돌려도 라 단어가 많으면 느립니다. 모든 단어를 한 번의 스캔으로 찾아야 합니다.
아호-코라식(Aho–Corasick)
- 모든 단어로 트라이를 만듭니다. 단어
k가 끝나는 노드를 기억해 둡니다. - 각 노드에 실패 링크를 붙입니다. 노드가 나타내는 문자열의 접미사 중, 트라이에 있는 가장 긴 진짜 접미사 노드입니다. BFS 순서로 KMP의 실패 함수처럼 구합니다.
- 글을 한 글자씩 읽으며 트라이를 따라가다가, 갈 수 없으면 실패 링크로 물러납니다. 각 글자를 읽은 뒤 도착한 노드의 방문 횟수를 1 늘립니다.
횟수 집계
노드 v에 도착했다는 것은 v의 문자열뿐 아니라 그 실패 링크를 따라가며 만나는 모든 노드의 문자열도 그 위치에서 끝났다는 뜻입니다. 실패 링크마다 일일이 따라가면 "aaaa…" 같은 입력에서 느려집니다. 대신 방문 횟수를 BFS 역순으로 실패 링크 부모에게 더해 주면(실패 트리의 서브트리 합) 노드마다 정확한 등장 횟수가 됩니다.
복잡도 목표
전체 입니다(). 단어마다 글을 다시 훑는 풀이는 효율성 테스트에서 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1140 ms | 도출됨 |
| Java 25 | 1356 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 10 | 판정만 |
| performance | 60 | 4 | 판정만 |