11903번 - 팰린드롬 세기

모의고사를 개최하고 싶었으나 낼 문제가 없었던 운영진은 생각나는 키워드인 '팰린드롬'과 '자료구조'를 혼합한 문제를 출제하기로 했습니다.

승현이는 여러분을 위해 알파벳 소문자로만 구성된 문자열 S를 만들었습니다. 편의상 S[i..j]를 S의 i번째 문자, (i+1)번째 문자, ..., (j−1)번째 문자, j번째 문자를 이어 붙인 부분문자열로 정의합시다. (단 1≤i≤j≤|S|)

여러분이 할 일은 S[a..b] (단 a≤b)의 부분문자열에서 팰린드롬이 몇 개나 있는지 세는 것입니다. 다시 말해, a≤x≤y≤b이고 S[x..y]가 팰린드롬인 두 정수의 순서쌍 (x,y)의 개수를 찾아내면 됩니다.

첫 번째 줄에 승현이가 만들어낸 문자열 S (1≤|S|≤100,000)가 주어집니다. 이 문자열은 알파벳 소문자 ('a', 'b', ..., 'z')로만 구성되어 있습니다.

두 번째 줄에 질의의 수 Q (1≤Q≤300,000)가 주어집니다. 다음 Q개 줄에 두 개의 정수 a_i와 b_i (1≤a_i≤b_i≤|S|)가 주어집니다. 각 질의에 대해서 여러분은 S[a_i..b_i]의 부분문자열들 중에 팰린드롬이 몇 개인지 세어야 합니다.

각 질의가 주어질 때마다 S[a_i..b_i]의 부분문자열들 중에 팰린드롬이 몇 개나 있는지 한 줄에 하나씩 출력합니다.

어떤 문자열 T=t₁t₂t₃⋯t_n이 팰린드롬이라는 것은 이것을 앞에서부터 뒤로 읽으나 뒤에서부터 앞으로 읽으나 같게 읽히는 것을 의미합니다. 즉,

t₁t₂t₃⋯t_n−1t_n=t_nt_n−1⋯t₃t₂t₁

를 만족하는 T는 팰린드롬입니다.

|S|는 문자열 S의 길이입니다.