CODE FESTIVAL 2016 qual B E - Lexicographical disorder

問題

E: Lexicographical disorder - CODE FESTIVAL 2016 qual B | AtCoder
N個の文字列Siが与えられる．以下のクエリにQ回答える問題
整数kと{'a',...,'z'}を並び替えたp1,...,p26が与えられる．文字の順序がp1<p2<...<p26の時SkはN個の文字列の中で何番目か

解法

Skより小さい文字列の数を高速に求めたい．トライ木を構成して各ノードで文字列の数を覚えておけばいいことがわかる．しかし，とても長い文字列が来ることがあるのでトライ木では間に合わない．トライ木のノードを圧縮して得られるパトリシア木を使うことで無駄な探索がなくなる．
パトリシア木の解説は気が向いたら+もっと綺麗にかけるようになったら...

ソースコード

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cassert>
using namespace std;

#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)
#define RREP3(i,s,e) for (i = s; i >= e; i--)
#define RREP2(i,n) RREP3 (i,(int)(n)-1,0)
#define RREP(...) GET_ARG (__VA_ARGS__,RREP3,RREP2) (__VA_ARGS__)
#define DEBUG(x) cerr << #x ": " << x << endl

struct Patricia {
    int num;
    bool end;
    string str;
    vector<Patricia*> children;
    Patricia() {}
    Patricia(string s) : str(s), num(1), end(true) {}
};

Patricia root;

void add(string s) {
    Patricia* node = &root;
    bool down = true;
    while (down && s.size() > 0) {
        down = false;
        for (auto ch: node->children) {
            if (ch->str[0] == s[0]) {
                int i;
                for (i = 0; i < min(ch->str.size(),s.size()) && ch->str[i] == s[i]; i++);
                if (i < ch->str.size()) {
                    Patricia* nnode = new Patricia(ch->str.substr(0,i));
                    nnode->children.push_back(ch);
                    nnode->num = ch->num+1;
                    nnode->end = false;
                    node->children.erase(find(node->children.begin(),node->children.end(),ch));
                    node->children.push_back(nnode);
                    ch->str.erase(0,i);
                    if (i == s.size()) {
                        nnode->end = true;
                    }
                    node = nnode;
                }
                else {
                    ch->num++;
                    if (i == s.size()) {
                        ch->end = true;
                    }
                    node = ch;
                }
                s.erase(0,i);
                down = true;
                break;
            }
        }
        if (!down) node->children.push_back(new Patricia(s));
    }
}

int pri[26];

int query(string s) {
    Patricia* node = &root;
    int ret = 0;
    while (s.size()) {
        Patricia* nxt;
        for (auto ch: node->children) {
            if (ch->str[0] == s[0]) {
                ret += ch->end;
                nxt = ch;
            }
            else if (pri[ch->str[0]-'a'] < pri[s[0]-'a']) {
                ret += ch->num;
            }
        }
        s.erase(0,nxt->str.size());
        node = nxt;
    }
    return ret;
}

string str[100000];

int main(void) {
    int i, n;
    scanf("%d\n",&n);
    REP (i,n) {
        char c;
        while (scanf("%c",&c), c != '\n') str[i] += c;
        add(str[i]);
    }
    int q;
    scanf("%d",&q);
    while (q--) {
        int k;
        scanf("%d ",&k);
        k--;
        char c;
        REP (i,26) {
            scanf("%c",&c);
            pri[c-'a'] = i;
        }
        printf("%d\n",query(str[k]));
    }
    return 0;
}