R00653
부분 문자열의 등장 횟수 질의
다이아몬드 III레이팅
의견: 0
설명
문자열 \(S\)가 주어진다. 각 질의는 두 정수 \(l, r\)로 주어지며, \(S\)의 부분 문자열 \(S[l..r]\)가 \(S\) 안에 (위치가 겹치는 것까지 포함하여) 몇 번 등장하는지를 출력해야 한다.
질의마다 직접 문자열을 탐색하면 너무 느리다.
제약
\(1 \le |S| \le 50{,}000\)
\(1 \le Q \le 100{,}000\)
\(1 \le l \le r \le |S|\)
입력 형식
첫 줄에 문자열 \(S\)가 주어진다 (소문자 알파벳).
둘째 줄에 질의 수 \(Q\).
이어서 \(Q\)개의 줄에 각각 \(l\)과 \(r\)이 주어진다.
출력 형식
각 질의에 대해 \(S[l..r]\)의 등장 횟수를 한 줄에 하나씩 출력한다.
예제 1
입력
abab
4
1 2
1 4
2 2
1 1
출력
2
1
2
2설명
S=abab. (1,2)=ab는 위치1,3에 등장 ->2. (1,4)=abab는 1번. (2,2)=b는 위치2,4 ->2. (1,1)=a는 위치1,3 ->2.
예제 2
입력
aaaa
3
1 1
1 2
1 4
출력
4
3
1설명
S=aaaa. a는 4번(겹침 포함). aa는 위치1,2,3에서 시작 ->3번. aaaa는 1번.
문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
부분 문자열의 등장 횟수 질의
개요
Log in to rate problems.
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
부분 문자열의 등장 횟수 질의
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기