题目概述

有一个文本串，现在有 $m$ 个模板串（互不相同），问文本串中长度最小的子串使得模板串出现了 $k_i$ 次。

解题报告

$m$ 个模板串互不相同奥妙重重，令 $M=\sum Length(m_i)$ ，因为互不相同，所以最多有 $\sqrt M$ 种不同的长度，而每种长度出现次数是 $O(M)$ 的，所以 $m$ 个串的出现位置是 $O(M\sqrt M)$ 级别的。

瞧我们发现了什么……这样不就可以暴力做了吗？只需要快速找到每个串在文本串中出现的位置，有两种选择：1.在线，后缀树。2.离线，AC自动机。AC自动机好写我就写了AC自动机，$fail$ 树上启发式合并就行了。

示例程序

注意如果vector+sort的话查询复杂度会多个 $log$ （然后我就T了），所以用set来启发式合并，这样虽然启发式合并复杂度多了 $log$ ，但set遍历是 $O(size)$ 的所以查询复杂度就可以不带 $log$ 了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
const int maxn=100000;

int n,te,w[maxn+5],len[maxn+5];char s[maxn+5],now[maxn+5];int v[maxn+5],p[maxn+5];
int si,son[maxn+5][26],fai[maxn+5],ID[maxn+5],que[maxn+5],ans[maxn+5];vector<int> e[maxn+5];
set<int> pos[maxn+5];set<int>::iterator it;

inline void Insert(char *s,int num,int p=0){
    for (int i=1;s[i];i++){
        int &now=son[p][s[i]-'a'];
        if (!now) now=++si;p=now;
    }ID[p]=num;
}
inline void getfail(){
    int Head=0,Tail=0;for (int i=0,u;i<26;i++) if (u=son[0][i]) fai[u]=0,que[++Tail]=u; else son[0][i]=0;
    while (Head!=Tail)
        for (int x=que[++Head],i=0,u;i<26;i++)
            if (u=son[x][i]) fai[u]=son[fai[x]][i],que[++Tail]=u;
            else son[x][i]=son[fai[x]][i];
    for (int i=1;i<=si;i++) e[fai[i]].push_back(i);
}
void getpos(int x){
    for (int j=0,si=e[x].size();j<si;j++){
        int u=e[x][j];getpos(u);if (pos[v[x]].size()<pos[v[u]].size()) swap(v[x],v[u]);
        for (it=pos[v[u]].begin();it!=pos[v[u]].end();it++) pos[v[x]].insert(*it);
    }
    if (ID[x]){
        int i=ID[x];if (pos[v[x]].size()<w[i]) {ans[i]=-1;return;}
        int m=0;for (it=pos[v[x]].begin();it!=pos[v[x]].end();it++) p[++m]=*it;
        ans[i]=p[w[i]]-p[1]+len[i];for (int j=w[i]+1;j<=m;j++) ans[i]=min(ans[i],p[j]-p[j-w[i]+1]+len[i]);
    }
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%s",s+1);n=strlen(s+1);scanf("%d",&te);
    for (int i=1;i<=te;i++) scanf("%d%s",&w[i],now+1),len[i]=strlen(now+1),Insert(now,i);
    getfail();for (int i=1;i<=si;i++) v[i]=i;
    for (int i=1,p=0;i<=n;i++) p=son[p][s[i]-'a'],pos[p].insert(i);
    getpos(0);for (int i=1;i<=te;i++) printf("%d\n",ans[i]);return 0;
}