[提交] [状态] [命题人:admin]

 

题目描述

奶牛 Bessie 很喜欢用手机上网聊天，但她的蹄子太大，经常会按到好几个键造成不必要的麻烦（丢死人了，你下辈子还是不要当奶牛了）。于是 Farmer John 给她专门设计了一套「自动完成 APP」。这个 APP 能够连接到在线词典来获取词库（词库的来源是 Bessie 常用的 n 个单词），并且有着自动补全的功能。当 Bessie 想打出她的一个常用单词时，她只需输入这个单词的某个前缀，并询问词库中拥有这个前缀的字典序第 k 小的单词，APP 就会返回这是词库中的第几个单词。
Farmer John 是个大忙人，所以编写 APP 的任务自然就交给了你。

 

输入

第一行两个整数 n,m，表示词库的单词个数和 Bessie 的询问次数。
接下来 n 行，每行一个字符串，表示 Bessie 的常用单词，输入的第 i 个字符串在词库中编号为 i。
接下来 m 行，每行一个整数 k 和一个字符串 S，表示 Bessie 的询问，意义是询问词库中以 S 为前缀的字典序第 k 小的单词在词库中的编号。

 

输出

对于每次询问输出一个整数，表示以S为前缀的字典序第 k 小的单词在词库中的编号；如果不存在这样的单词，输出 −1。

 

样例输入

复制样例数据

10 3
dab
ba
ab
daa
aa
aaa
aab
abc
ac
dadba
4 a
2 da
4 da

样例输出

3
1
-1

 

提示

(1) 以 a 为前缀的单词有 {aa,aaa,aab,ab,abc,ac}，其中字典序第 4 小的是 ab，是词库的第 3 个单词。
(2) 以 da 为前缀的单词有 {daa,dab,dadba}，其中字典序第 2 小的是 dab，是词库的第 1 个单词；没有第 4 小的单词。

对于 20% 的数据，1≤ 词库的字母总量,询问的字母总量 ≤103。
对于 100%的数据，1≤ 词库的字母总量,询问的字母总量 ≤106，保证词库里的单词两两不同，所有字符串只包含小写字母。

题目大意：中文题意

题目思路：考虑有前缀和所以用字典树去维护，但这个题用字典树维护仍然超时，仔细一想其实 遍历一波字典树，按26叉树来，输出单词库里的每一个单词，就是按照字典序来的，所以我们只需要根据DFS序给出的，只要这里有一个 以当前节点为结束的字符串我们就给他 标记一下，并且记录一下当前是第几个出现的，然后我们每次询问的前缀我们首先找到他是在哪个根结束的，并且如果过程中发现他没有根结束直接输出-1，然后判断一下这个根的前缀的个数是否>=k个，否则输出-1，在保证他一定有的情况下输出当前顺序的第 pos[rt]+k-1个就可以了。但需要注意一个小细节：树上的每一个节点都需要标记一下，下面有多少个而且需要编号 这是第几小的前缀。具体看一下代码(附上注释)：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e15+5;
const int maxn=1e6+8;
const double PI=acos(-1);
const ll mod=1e9+7;
ll n,m;
int num[maxn][30];
int cot[maxn];
bool vis[maxn];
int ans[maxn];
int s[maxn];
int r[maxn];
char str[maxn];
ll x=0;
ll cnt=0;
void build(char *st,int j)
{
    int rt=0,len=strlen(st);
    for(int i=0;i<len;i++)
    {
        ll temp=st[i]-'a'+1;
        if(!num[rt][temp])
            num[rt][temp]=++cnt;
        rt=num[rt][temp];
        cot[rt]++;
    }
    vis[rt]=true;//判断当前节点是否有字符串结束
    r[rt]=j;//当前节点结束的字符串属于第几个
}
//void Find()
void dfs(int rt)
{
    if(vis[rt]==true) {s[++x]=rt;ans[rt]=x;}//如果他有节点那这个地方就是 ++x个
    else ans[rt]=x+1;//否则 他也是第 x+1个（让他代表下面出现的第一个字符串），因为我们找的时候也是按x+1输出的第k个
    for(int i=1;i<=26;i++)
        if(num[rt][i])
            dfs(num[rt][i]);
}
ll Find(char *st)//首先找到原根
{
    int rt=0,len=strlen(st);
    for(int i=0;i<len;i++)
    {
        ll temp=st[i]-'a'+1;
        if(!num[rt][temp]) return -1;
        rt=num[rt][temp];
    }
    return rt;
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",str);
        build(str,i);
    }
    dfs(0);
    for(int i=1;i<=m;i++)
    {
        ll y;
        scanf("%lld%s",&y,str);
        ll res=Find(str);
        if(res==-1) printf("-1\n");
        else
        {
            if(cot[res]<y) printf("-1\n");
            else
                printf("%d\n",r[s[ans[res]+y-1]]);
        }
    }
    return 0;
}

总结：之前用字典树解决过一些问题，都没有写总结，趁着这个题在回忆一下字典树。处理字符串前缀匹配真的好用！