frequency with sa

#include <bits/stdc++.h>
#define MAX 100007

using namespace std;

struct state{
    int link, len, clone, pos;
    map<char, int> next;
    vector<int> parents;
} sa[2*MAX];

char s[MAX], t[MAX];
int sz, last;
void init(){
    last = 0;
    sa[0].link = -1;
    sa[0].len = 0;
    sz = 1;
}

void add(char c){
    int cur = sz++;
    sa[cur].len = sa[last].len + 1;
    sa[cur].pos = sa[last].len;
    for(; last != -1 && !sa[last].next.count(c); last = sa[last].link) sa[last].next[c] = cur;

    if(last == -1) sa[cur].link = 0;
    else{
        int q = sa[last].next[c];
        if(sa[q].len == sa[last].len + 1) sa[cur].link = q;
        else{
            int clone = sz++;
            sa[clone].len = sa[last].len + 1;
            sa[clone].pos = sa[q].pos;
            sa[clone].link = sa[q].link;
            sa[clone].clone = true;
            sa[clone].next = sa[q].next;
            for(; last != -1 && sa[last].next[c] == q; last = sa[last].link) sa[last].next[c] = clone;
            sa[cur].link = sa[q].link = clone;
        }
    }
    last = cur;
}

vector<int> l;
void dfs(int id, int size){
    if(!sa[id].clone) l.push_back(sa[id].pos);
    for(int i = 0; i < sa[id].parents.size(); i++) dfs(sa[id].parents[i], size);
}

int qnt;
void process(int size){
    int i = 0, v = 0;
    for(; i < size; i++) {
        if(!sa[v].next.count(t[i])){
            printf("-1\n");
            return;
        }
        v = sa[v].next[t[i]];
    }
    l.clear();
    dfs(v, size);
    sort(l.begin(), l.end());
    if(l.size() >= qnt){
        int ans = 100000000;
        //for(i = 0; i < l.size(); i++) cout << l[i] << " ";
        //cout << endl;
        for(i = qnt-1; i < l.size(); i++){
            ans = min(ans, l[i]-l[i-qnt+1]+size);
        }
        printf("%d\n", ans);
        return;
    }
    printf("-1\n");
}
int main(){
    scanf(" %s", s);
    int xuxu = strlen(s);
    init(); for(int i = 0; i < xuxu; i++) add(s[i]);

    for(int i = 1; i < sz; i++){
        sa[sa[i].link].parents.push_back(i);
    }

    int cases; scanf("%d", &cases);
    while(cases--){
        scanf("%d %s", &qnt,t);
        process(strlen(t));
    }
    return 0;
}