주문서 롤링 해시 카운터
실버 I의견: 0
마법사 우체국에는 길이 \(n\)인 문자열로 된 주문서 \(T\)가 보관되어 있다. 우편 분류기는 \(Q\)개의 패턴 문자열이 주어지면, 각 패턴이 \(T\) 안에 몇 번 등장하는지 세어 준다. 겹치는 등장도 모두 셈에 포함한다.
예를 들어 \(T = \text{aba}\)이고 패턴이 \(\text{a}\)이면 위치 \(1\), \(3\)에서 등장해 \(2\)번이다.
- \(1 \le n \le 200\,000\)
- \(1 \le Q \le 200\)
- 각 패턴의 길이는 \(1\) 이상 \(n\) 이하이다.
- 모든 패턴 길이의 합은 \(200\,000\) 이하이다.
- \(T\)와 모든 패턴은 알파벳 소문자로만 이루어진다.
첫째 줄에 주문서의 길이 \(n\)과 패턴 수 \(Q\)가 공백으로 구분되어 주어진다.
둘째 줄에 알파벳 소문자로만 이루어진 길이 \(n\)의 문자열 \(T\)가 주어진다.
다음 \(Q\)개의 줄에 패턴이 하나씩 주어진다. 각 패턴은 알파벳 소문자로만 이루어진다.
\(Q\)개의 줄에 걸쳐 각 패턴이 \(T\)에 등장하는 횟수를 입력 순서대로 출력한다.
8 3
abababab
ab
aba
bab
4
3
3
ab는 위치 \(1,3,5,7\)에서 \(4\)번 등장한다. aba는 위치 \(1,3,5\)에서 \(3\)번 등장한다. bab는 위치 \(2,4,6\)에서 \(3\)번 등장한다. 겹치는 등장도 모두 셈에 포함된다.
11 4
mississippi
issi
ss
ippi
xyz
2
2
1
0
issi는 위치 \(2,5\)에서 \(2\)번 등장한다. ss는 위치 \(3,5\)에서 \(2\)번 등장한다. ippi는 위치 \(8\)에서 \(1\)번 등장한다. xyz는 등장하지 않아 \(0\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
주문서 롤링 해시 카운터
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
주문서 롤링 해시 카운터