미하일의 문제
시간 제한3초메모리 제한512 MB
문자열 s와 여러 질의 구간 [l, r]이 주어질 때, 각 구간 s[l..r] 안에 있는 서로 다른 회문 부분 문자열의 개수를 구합니다.
문제
문자열 와 여러 개의 질의가 주어진다. 번째 질의에서는 에 들어 있는 서로 다른 회문 부분 문자열의 개수를 구한다. 부분 문자열을 앞에서 읽으나 뒤에서 읽으나 같으면 회문이다. 두 부분 문자열이 문자열로서 다르면 서로 다른 것으로 본다.
입력
첫째 줄에 소문자 알파벳으로 이루어진 비어 있지 않은 문자열 가 주어진다. 길이는 이하이다.
둘째 줄에 질의의 개수 ()가 주어진다. 이어지는 개의 줄에는 공백으로 구분된 두 정수 와 가 한 줄에 하나씩 주어진다 ().
출력
개의 줄을 출력한다. 번째 줄에는 번째 질의의 답을 출력한다.