전산생물학

바이트아저씨(Byteasar)는 바이트랜드 전산생물학 연구소에서 일한다. 방금 길이가 $n$인 유전체(genome) 문자열을 받았고, 그 안에서 가장 자주 나타나는 순환 조각을 찾으려 한다.

이 문자열은 대문자 알파벳으로 이루어진 단어 $s = s_1 s_2 \ldots s_n$으로 나타낸다. 어떤 단어의 순환 회전(cyclic rotation) 은 맨 뒤 글자를 맨 앞으로 옮기는 연산을 (필요하면 여러 번) 적용해 얻는 단어다. 예를 들어 ABAABA 의 서로 다른 순환 회전은 ABAABA, BAABAA, AABAAB 세 가지다. 단어 $u$가 단어 $v$의 부분단어(subword) 라는 것은, $u$가 $v$에서 연속한 글자들의 한 덩어리로 나타난다는 뜻이다.

단어 $t$가 $s$의 순환 조각(cyclic fragment) 이라는 것은, $t$의 모든 순환 회전이 $s$의 부분단어라는 뜻이다. 이러한 $t$에 대해 $s$에서의 순환 출현 횟수는, $t$의 서로 다른 순환 회전들이 $s$에 나타나는 횟수의 총합으로 정의한다.

각 질의로 주어지는 길이 $m$에 대해, 길이가 $m$인 $s$의 순환 조각이 가질 수 있는 순환 출현 횟수의 최댓값을 구하라. 길이가 $m$인 순환 조각이 존재하지 않으면 답은 0이다.

첫째 줄에 두 정수 $n$과 $q$가 주어진다 ($2 \le n \le 500{,}000$, $1 \le q \le 8$). 각각 유전체 문자열의 길이와 질의의 개수를 뜻한다. 둘째 줄에는 대문자 알파벳 $n$개로 이루어진 단어 $s$가 주어진다. 이어지는 $q$개의 줄에는 각 줄마다 정수 $m_i$ ($2 \le m_i \le n$)가 하나씩 주어지며, 그 질의에서 살펴볼 순환 조각의 길이를 뜻한다.

$q$개의 줄을 출력한다. $i$번째 줄에는 길이가 $m_i$인 $s$의 순환 조각들 중 순환 출현 횟수의 최댓값을 정수 하나로 출력한다 (존재하지 않으면 0).

$s$가 AABAABACDABAABAA 인 경우를 보자. 길이 6에서 순환 조각 AABAAB 은 서로 다른 순환 회전 세 개를 가지며, 이들은 $s$에서 모두 합쳐 4번 나타난다: AABAAB 으로 1번, ABAABA 로 2번, BAABAA 로 1번. 길이 6짜리 어떤 순환 조각도 이보다 많지 않으므로 답은 4다. 길이 3에서는 순환 조각 AAB 이 회전 AAB, ABA, BAA 를 통해 모두 합쳐 10번 나타나며, 이것이 최댓값이다.