맨버마이어스

[Hsue66]

include

define MAX 402

int t, n, K, res; int SA[MAX], g[MAX], tg[MAX], buf[MAX];

int ztrlen(char str) { int c = 0; while (str++) c++; return c; }

int cmp(int x, int y) { if (g[x] == g[y]) return g[x + t] < g[y + t]; else return g[x] < g[y]; }

void mergesort(int *p, int len) { if (len < 2) return; int i, j, k, mid; i = k = 0; j = mid = len / 2;

mergesort(p, mid);
mergesort(p + mid, len - mid);

while (i < mid && j < len) {
    if (cmp(p[i],p[j]))
        buf[k++] = p[i++];
    else
        buf[k++] = p[j++];
}

while(i<mid)
    buf[k++] = p[i++];
while (j < len)
    buf[k++] = p[j++];

for (int i = 0; i < len; i++)
    p[i] = buf[i];

}

void getSA(char *str) { t = 1; n = ztrlen(str); for (int i = 0; i < n; i++) { SA[i] = i; g[i] = str[i] - 'a'; } while (t <= n) { g[n] = -1; mergesort(SA, n); tg[SA[0]] = 0; for (int i = 1; i < n; i++) { if (cmp(SA[i - 1], SA[i])) tg[SA[i]] = tg[SA[i - 1]] + 1; else tg[SA[i]] = tg[SA[i - 1]]; }

    for (int i = 0; i < n; i++) {
        g[i] = tg[i];
        if (g[i] == K - 1)
            res = i;
    }
    t <<= 1;
}

}

int main() { int testcase; scanf("%d", &testcase); for (int tc = 0; tc < testcase; tc++) { scanf("%d", &K); char str[MAX]; scanf("%s", str);

    getSA(str);
    printf("#%d ", tc + 1);
    for (int i = res; i < n; i++)
        printf("%c", str[i]);
    printf("\n");
}

}