정올 동물원에는 많은 동물들이 있다.

대부분의 동물들은 아무런 일도 하지 않고 게으른 상태였으며 사육사 재민이는 이런 분위기가 마음에 들지 않았다.

그래서 재민이는 동물들에게 KMP 알고리즘을 가르치기로 했다.

재민 : 길이 L의 문자열 S가 주어진다면 O(L)의 시간에 실패함수 fail[]을 구할 수 있어요. 혹시 fail[]의 의미를 아는 동물 있나요?

판다 : fail[i]는 S를 1~i 까지 보았을 때 접두사와 접미사가 일치하는 최대 길이를 의미합니다.

재민 : 잘했어요! 혹시 예시를 줄 수 있나요?

판다 : S="abcababc"라고 하면 fail[5]=2입니다. "ab"는 "abcab"의 접두사이자 접미사이며 가장 긴 문자열입니다. 따라서 2에요. 같은 방식으로 fail[8]은 abc가 성질을 만족하는 가장 긴 문자열이므로 3이 됩니다.

재민이는 판다를 칭찬해주었다. 그리고 수업을 마치기 전, 동물들에게 한 가지 숙제를 내주었다.

재민이는 fail[] 대신 num[]을 정의해, 이를 구하는 것을 숙제로 냈다.

재민이의 정의에 따르면 num[i] (1<=i<=N)은 S를 1~i까지 보았을 때, 그 문자열에서 접두사와 접미사가 동일하고 둘이 '겹치지 않는' 것의 개수를 의미한다.

여기서 겹치지 않는다는 것은 S상에서 같은 문자를 동시에 포함하지 않는다는 의미이다.

가령 S="aaaaa"라고 하면, 접두사 "aaa"와 접미사 "aaa"는 동일하지만 S에서의 위치 상 둘 다 세 번째 a를 공유하므로 겹쳐 조건을 만족하지 않는다.

S="aaaaa"라고 하면 num[]은 0, 1, 1, 2, 2의 배열이 된다.

재민이는 숙제에 초콜릿을 상품으로 걸었다.

펭귄은 이 이야기를 듣고 눈이 반짝거리기 시작했다.

하지만 펭귄은 수업 내내 자서 문제를 풀 수가 없었고 귀여운 표정을 지으면서 당신에게 도움을 요청했다.

N개의 문자열 S가 주어지면 각 S에 대해 num을 구하는 프로그램을 작성해서 펭귄을 도와주자.

단, 출력량이 매우 많을 수 있으므로 N개의 num 배열을 전부 출력하는 대신 각 S마다 (num[i]+1)을 모두 곱한 값을 10억 7로 나눈 나머지를 출력하라.

동물원 timer 1s memory 512MB

동물원 1s 512MB