반복 재생 구간

문제

음악 스트리밍 서비스의 재생 목록은 곡마다 소문자 한 글자의 코드를 붙여 만든 길이 N의 문자열 S 로 나타낸다. 서비스는 목록의 일부 구간을 눈에 띄게 반복해서 재생하는 구간인지 알아보려 한다. 구간 [l, r] 에 해당하는 부분 문자열이 어떤 비어 있지 않은 문자열 u 를 k번 이어 붙인 것(k ≥ 1)일 때, 그런 표현 중 k 가 가장 큰 것을 그 구간의 반복 횟수라고 한다. u 가 가장 짧을 때 k 가 가장 크다. 예를 들어 abababcabcabc 에서 처음 6글자 ababab 의 반복 횟수는 3 이고, 마지막 6글자 abcabc 의 반복 횟수는 2 이다. cabcabc 처럼 더 짧은 문자열의 반복으로 나타낼 수 없는 구간은 반복 횟수가 1 이다. 길이가 1 인 구간의 반복 횟수도 1 이다. 구간의 부분 문자열이 u 를 이어 붙인 것이어야 하며, 마지막에 u 의 일부만 남는 경우는 반복으로 치지 않는다. 질문이 Q개 주어질 때, 각 질문의 구간 [l, r] 의 반복 횟수를 구하는 프로그램을 작성하라. 문자의 위치는 1부터 센다.

입력

첫째 줄에 N과 Q(1 ≤ N, Q ≤ 200,000)가 공백으로 구분되어 주어진다. 둘째 줄에 소문자로만 이루어진 길이 N의 문자열 S 가 주어진다. 이어지는 Q개의 줄에 각각 질문 l, r(1 ≤ l ≤ r ≤ N)이 공백으로 구분되어 주어진다.

출력

각 질문마다 한 줄에 해당 구간의 반복 횟수를 출력한다.

13 7
abababcabcabc
1 6
1 4
7 13
8 13
1 5
2 7
3 3

3
2
1
2
1
1
1

4 3
aaaa
1 4
2 3
1 1

4
2
1

출처: Devin.KR 자체 제작