접두사마다 팰린드롬 세기
다이아몬드 III의견: 0
문자열 \(S\)가 주어진다. 각 질의는 정수 \(r\)로 주어지며, \(S\)의 접두사 \(S[1..r]\)에 대하여 다음 두 값을 구해야 한다.
-
\(S[1..r]\) 안에 등장하는 서로 다른 팰린드롬 부분 문자열의 개수 \(A\).
-
\(S[1..r]\) 안의 팰린드롬 부분 문자열의 총 등장 횟수 \(B\) (같은 문자열이라도 위치가 다르면 각각 센다).
한 접두사 안에 팰린드롬은 최대 \(\Theta(r^2)\)번 등장할 수 있으므로 단순 열거로는 풀 수 없다.
\(1 \le |S| \le 200{,}000\)
\(1 \le Q \le 200{,}000\)
\(1 \le r \le |S|\)
첫 줄에 문자열 \(S\)가 주어진다 (소문자 알파벳).
둘째 줄에 질의의 수 \(Q\).
이어서 \(Q\)개의 줄에 각각 정수 \(r\)이 주어진다.
각 질의마다 두 정수 \(A\)와 \(B\)를 공백으로 구분하여 한 줄에 출력한다.
abba
4
1
2
3
4
1 1
2 2
3 4
4 6r=1: a (서로다름1, 등장1). r=2: a,b (2, 2). r=3: a,b,bb (3, 등장 a,b,b,bb=4). r=4: a,b,bb,abba (4, 등장 a,b,b,a,bb,abba=6).
aaa
3
3
2
1
3 6
2 3
1 1aaa의 서로 다른 회문은 a,aa,aaa로 r=3에서 3개. 등장 횟수는 a 3번, aa 2번, aaa 1번 = 6. r=2: 서로다름 a,aa=2, 등장 a,a,aa=3. r=1: 1, 1.
riseoj 작성
출처 Original
평가 및 의견
접두사마다 팰린드롬 세기
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
접두사마다 팰린드롬 세기