#include <stdio.h>
#define MOD 1000011
#define MAX_L 15
//#define MAX_L 200001
int L;
char S[MAX_L];
int hashtable[MOD][4];
long long MULTI[MAX_L];
int checkHash(int n) {
int i, j, k;
long long h = 0;
for (i = 0; i < n; i++) {
h += (S[i] * MULTI[n - i - 1]) % MOD;
}
h = h % MOD;
hashtable[h][0] = n;
hashtable[h][1] = 0;
for (i = 1; i <= L - n; i++) {
h -= S[i - 1] * MULTI[n - 1];
h %= MOD;
while (h < 0)
{
h += MOD;
}
h = h * 26;
h += S[i - 1 + n];
h = h % MOD;
if (hashtable[h][0] == n) {
for (k = 0; k < n; k++) {
if (S[hashtable[h][1] + k] != S[i + k]) {
break;
}
}
if (k == n) {
return n;
}
else {
if (hashtable[h][2] == n) {
for (k = 0; k < n; k++) {
if (S[hashtable[h][3] + k] != S[i + k]) {
break;
}
}
if (k == n) {
return n;
}
}
hashtable[h][2] = n;
hashtable[h][3] = i;
}
}
else {
hashtable[h][0] = n;
hashtable[h][1] = i;
}
}
return 0;
}
int main(void)
{
freopen("input.txt", "r", stdin);
int test_case, left, right;
int T, i, j, k;
MULTI[0] = 1;
for (i = 1; i < MAX_L; i++) {
MULTI[i] = MULTI[i - 1] * 26 % MOD;
}
setbuf(stdout, NULL);
scanf("%d", &T);
for (test_case = 1; test_case <= T; ++test_case)
{
// init
int answer = 0;
for (i = 0; i < MOD; i++) {
hashtable[i][0] = hashtable[i][1] = hashtable[i][2] = hashtable[i][3] = 0;
}
scanf("%d", &L);
scanf("%s", S);
left = 0;
right = L - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (checkHash(mid)) {
left = mid + 1;
answer = (mid > answer) ? mid : answer;
}
else {
right = mid - 1;
}
}
printf("#%d %d\n", test_case, answer);
}
return 0; //정상종료시 반드시 0을 리턴해야 합니다.
}
댓글