12786 自动完成 APP

把字符串读进来的时候顺便记录一下这个字符串的位置,然后排序。对于每个输入的前缀,用一个lower_bound找到满足这个前缀的第一个字符串,然后再加上K判断下这个这个字符串是否存在,如果存在就输出,否则就输出“-1”。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<pair<string,int> > vec;
const int maxn = 1e6+10;
int m,n,k;
char ch[maxn];
int main()
{
    scanf("%d%d",&n, &m);
    for(int i = 0;i < n; i++)
        scanf("%s",ch),vec.push_back(make_pair(ch,i));
    sort(vec.begin(),vec.end());
    for(int i = 0;i < m; i++)
    {
        scanf("%d%s",&k ,ch);
        string s = ch;
        int first = lower_bound(vec.begin(),vec.end(),make_pair(s,0)) - vec.begin();
        if(first + k - 1 < vec.size() && (vec[first + k - 1].first.size() >= s.size() && vec[first + k - 1].first.substr(0,s.size()) == s))
            printf("%d\n",vec[first + k - 1].second + 1);
        else
            puts("-1");
    }
    return 0;
}