后缀数组笔记。

首先只要学过 SA 就并不难刻画“恰好出现 $k$ 次”这一条件。
设 $u$ 为 $[l,r]$ height 的 $\min$，且 $r-l+1$ 即区间长度为定值 $k-1$，这个可以用单调队列简单维护。
则 $[1,u]$ 的前缀出现次数显然不小于 $k$，至于恰好为 $k$ 只需要钦定 $d = \max(ht_{l-1},ht_{r+1})$ 就行了，合法的长度区间为 $[d+1,u]$，相当于这个区间出现次数 $+1$。
现在需要一个数据结构支持区间 $+1$ 和全局查询最大值。由于查询在加法之后因此可以用差分。

对于 $k=1$，由于单调队列区间长度为 $k-1=0$，需要特殊处理它的 $u$ 为 $n-sa_i+1$ 即后缀长度。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int T, n, k;
char s[N];

int x[N], y[N], rk[N], sa[N], cnt[N];
void init_SA() {
    int v = 128;
    for (int i = 0; i <= v; i++) cnt[i] = 0;
    for (int i = 1; i <= n; i++) ++cnt[x[i] = s[i]];
    for (int i = 1; i <= v; i++) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; i--) sa[ cnt[x[i]]-- ] = i;
    for (int len = 1; ; len <<= 1) {
        int tot = 0;
        for (int i = n - len + 1; i <= n; i++) y[++tot] = i;
        for (int i = 1; i <= n; i++)
            if (sa[i] > len) y[++tot] = sa[i] - len;

        for (int i = 0; i <= v; i++) cnt[i] = 0;
        for (int i = 1; i <= n; i++) ++cnt[x[i]];
        for (int i = 1; i <= v; i++) cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; i--) sa[ cnt[x[y[i]]]-- ] = y[i];

        swap(x, y), tot = 0;
        for (int i = 1; i <= n; i++) {
            if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + len] == y[sa[i - 1] + len]) x[sa[i]] = tot;
            else x[sa[i]] = ++tot;
        }
        v = tot;
        if (v == n) break;
    }
}

int ht[N];
void init_height() {
    for (int i = 1; i <= n; i++) rk[sa[i]] = i;
    for (int i = 1, j = 0, now = 0; i <= n; i++) {
        if (rk[i] == 1) { ht[rk[i]] = 0; continue; }
        j = sa[rk[i] - 1], now = max(now - 1, 0);
        while (i + now <= n && j + now <= n && s[i + now] == s[j + now]) now++;
        ht[rk[i]] = now;
    }
}

int q[N], st, ed;
int b[N];
void solve() {
    for (int i = 1; i < k; i++) {
        while (st <= ed && ht[q[ed]] > ht[i]) ed--;
        q[++ed] = i;
    }
    for (int i = k; i <= n; i++) {
        while (st <= ed && q[st] <= i - k + 1) st++;
        while (st <= ed && ht[q[ed]] > ht[i]) ed--;
        q[++ed] = i;
        int l = ht[i - k + 1], r = ht[i + 1];
        int u = (k == 1) ? (n - sa[i] + 1) : ht[q[st]], d = max(l, r) + 1;
        if (d <= u) b[d]++, b[u + 1]--;
    }
    int Max = 0, id = 0;
    for (int i = 1; i <= n; i++) {
        b[i] += b[i - 1];
        if (Max <= b[i]) Max = b[i], id = i;
    }
    printf("%d\n", (Max == 0) ? -1 : id);
}

void clr() {
    for (int i = 0; i <= ed; i++) q[i] = 0; st = 1, ed = 0; //clr
    for (int i = 0; i <= n + 1; i++) b[i] = sa[i] = rk[i] = ht[i] = 0;
}

void mian() {
    scanf("\n %s %d", s + 1, &k), n = strlen(s + 1);
    clr();
    init_SA();
    init_height();
    solve();
}

int main() {
    scanf("%d", &T);
    while (T--) mian();
    return 0;
}