12786 自动完成 APP

直接用字典树会TLE,需要用dfs序进行优化。

#include <iostream>

using namespace std;
typedef long long ll;
const ll maxn = 1000005;
struct Node {
    int cnt;
    int nxt[26];
    int endId;
    int l,r;
} node[maxn];
int tot = 1;

void insert(char s[], int id) {
    int p = 1, i = 0;
    for (; s[i]; i++) {
        int j = s[i] - 'a';
        if (node[p].nxt[j] == 0) {
            node[p].nxt[j] = ++tot;
        }
        node[p].cnt++;
        p = node[p].nxt[j];
    }
    node[p].cnt++;
    node[p].endId = id;
}

int v[maxn],cnt;

void dfs(int p) {
    node[p].l = cnt;
    if (node[p].endId!=0)
        v[cnt++]=node[p].endId;
    for (int j=0;j<26;j++) {
        if (node[p].nxt[j]!=0) {
            dfs(node[p].nxt[j]);
        }
    }
    node[p].r=cnt;
}

int search(char s[], int k) {
    if (k<=0)
        return -1;
    int p = 1;
    for (int i = 0; s[i]; i++) {
        int j = s[i] - 'a';
        p = node[p].nxt[j];
        if (p == 0) return -1;
        if (node[p].cnt < k ) return -1;
    }
    int ans = v[node[p].l+k-1];
    return ans;
}

char s[maxn];

int main() {

    int n, m, k;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s);
        insert(s, i);
    }
    dfs(1);
    for (int i = 1; i <= m; i++) {
        scanf("%d", &k);
        scanf("%s", s);
        int ans = search(s, k);
        printf("%d\n", ans);
    }

    return 0;
}