题解 P2237 【[USACO14FEB]自动完成Auto-complete】

Expecto · 2016-09-28 13:26:14 · 题解

先把字典排个序，之后lower_bound 下前缀的位置，加上k就好了

#include<bits/stdc++.h>
using namespace std;
pair<string ,int> a[90030];
bool match(string x,string y){
    if (y.length()>x.length()) return 0;
    return x.substr(0,y.size())==y;
}
int main(){
    int w,n;
    cin>>w>>n;
    for (int i=0;i<w;i++){
        cin>>a[i].first;
        a[i].second=i;
    }
    sort(a,a+w);
    while (n--){
        string pre;
        int k;
        cin>>k>>pre;
        int pos=k-1+lower_bound(a,a+w,make_pair(pre,0))-a;
        if (pos>=w || !match(a[pos].first,pre)) {
            cout<<"-1\n";
            continue;
        }
        cout<<a[pos].second+1<<'\n';
    }
    return 0;
}