本文共 1640 字，大约阅读时间需要 5 分钟。

感想

一开始看错题了。。

题解

注意，下文全部的字典树都是倒着建的

1可持久化tri 我的O(nlogn)

你就建一个可持久化tri，然后你就二分一下答案，在1~i这颗字典树上走到这个字符串对应的节点。。

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int N=300005*2;struct qq{    int son[26];    int c;//在多少个串中出现过 }s[N];int num=0;int L[N],R[N],cnt;char s1[N];int n;char ss[N];int root[N];//前i个串void Ins (int &rt1,int x,int rt2){    if (x==-1) return ;    if (rt1==0) rt1=++num;    s[rt1].c=s[rt2].c+1;    int c=ss[x]-'a';    Ins(s[rt1].son[c],x-1,s[rt2].son[c]);    for (int u=0;u<26;u++)        if (u!=c)            s[rt1].son[u]=s[rt2].son[u];}int k;int check (int now,int x)//前多少个字符串     第几个字符串去匹配{    now=root[now];    for (int u=R[x];u>=L[x];u--)    {        int c=s1[u]-'a';        now=s[now].son[c];    }    return s[now].c;}int main(){    s[0].c=0;    scanf("%d",&n);    for (int u=1;u<=n;u++)    {        scanf("%s",ss+1);int len=strlen(ss+1);        Ins(root[u],len,root[u-1]);        L[u]=cnt+1;        for (int i=1;i<=len;i++) s1[++cnt]=ss[i];        R[u]=cnt;    }    for (int u=1;u<=n;u++)    {        scanf("%d",&k);         int ans=-1;        int l=1,r=n;        while (l<=r)        {            int mid=(l+r)>>1;            if (check(mid,u)>=k) {ans=mid;r=mid-1;}            else l=mid+1;        }        printf("%d\n",ans);    }    return 0;}
      
     
    
   

2 乱七八糟的方法O(nlogn)【但是不可以有重复的串】

我们可以吧串从小到大插入，可以知道一个串的Kpm串肯定是在他后面的

3 比较优的做法O(n)

大概就是把2的方法，按时间顺序插入，然后我们将他路过的点都加上他自己的信息。。

4网上烂大街的做法O(nlogn)

就是dfs序+主席树，我也没有认真看，不写了