구간 속 부분문자열 세기
다이아몬드 I의견: 0
길이 \(N\)의 문자열 \(S\)가 주어진다. \(S\)의 문자는 1번부터 \(N\)번까지 번호가 매겨져 있다.
이후 \(Q\)개의 질의가 주어진다. 각 질의는 네 정수 \(l, r, a, b\)로 이루어진다.
각 질의에 대해, 패턴 \(P = S[a..b]\) (즉 \(S\)의 \(a\)번째부터 \(b\)번째 문자까지)가, 구간 \(S[l..r]\) 안에서 몇 번 등장하는지 세어 출력해야 한다.
여기서 "등장"이란, 시작 위치 \(i\)가 \(l \le i\) 이고 끝 위치 \(i + |P| - 1 \le r\) 를 만족하면서 \(S[i..i+|P|-1] = P\) 인 경우를 말한다. 즉 패턴이 구간 \([l, r]\) 안에 완전히 들어가야 한다. 겹치는 등장도 각각 센다.
\(1 \le N \le 100{,}000\)
\(1 \le Q \le 100{,}000\)
\(1 \le l \le r \le N\), \(1 \le a \le b \le N\)
첫 줄에 정수 \(N\)이 주어진다.
둘째 줄에 길이 \(N\)의 문자열 \(S\)가 주어진다 (영소문자 a–z로만 이루어진다).
셋째 줄에 질의 수 \(Q\)가 주어진다.
이어서 \(Q\)개의 줄에 각각 네 정수 \(l, r, a, b\)가 주어진다 (\(1 \le l \le r \le N\), \(1 \le a \le b \le N\)).
각 질의에 대해 패턴이 구간 안에서 등장하는 횟수를 한 줄에 하나씩 출력한다.
5
ababa
4
1 5 1 2
1 5 1 3
2 5 1 2
1 4 3 5
2
2
1
1S=ababa. 질의1: 패턴 ab가 [1,5] 전체에서 위치1,3에 2번 등장. 질의2: 패턴 aba가 위치1,3에 2번(겹침 허용). 질의3: 패턴 ab가 [2,5]에 들어가는 등장은 위치3뿐이라 1. 질의4: 패턴 aba(=S[3..5])가 [1,4] 안에 완전히 들어가려면 끝위치<=4여야 하는데 길이3이라 시작은 1,2만 가능, 위치1의 aba만 들어가 1.
4
aaaa
3
1 4 1 1
1 4 1 2
2 3 1 1
4
3
2S=aaaa. 질의1: 패턴 a는 [1,4]에서 4번 등장. 질의2: 패턴 aa는 위치1,2,3에 3번 등장. 질의3: 패턴 a는 구간 [2,3] 안에서 위치2,3에 2번 등장.
riseoj 작성
출처 Original
평가 및 의견
구간 속 부분문자열 세기
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
구간 속 부분문자열 세기