ICPC-JAG Day4 Problem F

ICPC JAG

解説では，Suffix Array + Range Minimum Queryでの解法が紹介されていましたが，僕はクエリ先読み + Aho-Corasick法で通しました．というか，Suffix Arrayよくわかってない．

ある人には，「クエリ先読みするなよ」と言われました．

概要

文字列SとQ個のクエリが与えられる．
i番目のクエリは2つの文字列x[i], y[i]で表現され，クエリに対してSの部分文字列の中でx[i]で始まりy[i]で終わるものを探す．

方針

クエリを先読みし，オートマトンをつくり，Sの中でx[i]が初めに出現するところと，y[i]が最後に出現するところを探す．
Sと全てのy[i]を前後逆にしてしまえば，両方とも全く同じアルゴリズムでよい．

Aho-Corasick法のマッチングを全部取っていくのは無駄．例えば，a, aa, aaa, ... みたいなケースが来たときに，aの判定を真面目にやると計算量が大きくなって時間的にもメモリ的にもつらい．これを改善するため，各状態について受理された文字列の判定は1回だけしか行わない．その時点で受理された文字列があるかの判定は，失敗したとき用のリンクを使って根か，既に判定済みの状態に到達するまでさかのぼることで行う．

ライブラリ写して，ちょっと手を加えて，簡単な実装やるだけだった．ライブラリになっているとはいえ，そこそこ実装コストがある．ただ，聞いた話だとSuffix Arrayも似たようなぐらいの実装量が必要になるらしい．そこにRMQの実装も加わるので，実装コストはこっちの方が若干軽いのかもしれない．

#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define ALL(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;

string S;
int m;
vector<string> vx, vy;

struct PMA{
    int id;
    PMA *next[30];
    vector<int> accept;
    bool flag;
    PMA() { fill(next, next+30, (PMA*) NULL); flag = false; }
};
void buildPMA(const vector<string> &words, vector<PMA*> &vp){
    int n = words.size();
    PMA *root = new PMA();
    root -> id = 0;
    vp.push_back(root);
    int count = 1;
    for(int i = 0; i < n; ++i){
        PMA* v = root;
        int m = words[i].size();
        for(int j = 0; j < m; ++j){
            int c = words[i][j] - 'a'+1;
            if(v->next[c] == NULL){
                v->next[c] = new PMA;
                v->next[c] -> id = count++;
                vp.push_back(v->next[c]);
            }
            v = v->next[c];
        }
        v->accept.push_back(i);
    }
    queue<PMA*> Q;
    root->next[0] = root;
    for(int c = 1; c < 27; ++c){
        if(root->next[c] != NULL){
            root ->next[c]->next[0] = root;
            Q.push(root->next[c]);
        } else root->next[c] = root;
    }
    while(!Q.empty()){
        PMA *v = Q.front(); Q.pop();
        for(int c = 1; c < 27; ++c){
            if(v->next[c] != NULL)
                Q.push(v->next[c]);
            PMA *r = v->next[0];
            while(r->next[c]==NULL) r = r->next[0];
            if(v->next[c] != NULL)
                v->next[c] ->next[0] = r->next[c];
            else
                v->next[c] = r->next[c];
        }
    }
}
void searchfirst(const string &s, const vector<string> &word, vector<int> &r){
    vector<PMA*> vp;
    buildPMA(word, vp);
    PMA *p = vp[0];

    for(int i = 0; i < s.size(); ++i){
        p = p->next[s[i]-'a'+1];
        PMA *q = p;
        while(!(q->flag)){
            EACH(j, q->accept){
                r[*j] = i-word[*j].size() + 1;
            }
            q->flag = true;
            q=q->next[0];
        }
    }
}
int main(){
    cin >> S >> m;
    for(int i = 0; i < m; ++i){
        string x, y;
        cin >> x >> y;
        reverse(ALL(y));
        vx.push_back(x);
        vy.push_back(y);
    }
    vector<int> rx(m, -1), ry(m,-1);
    searchfirst(S, vx, rx);
    reverse(ALL(S));
    searchfirst(S, vy, ry);
    for(int i = 0; i < m; ++i){
        int idx = S.size()-ry[i];
        if(idx < rx[i]+vx[i].size() || rx[i] < 0 || ry[i] < 0){
            printf("0\n");
        }
        else{
            printf("%d\n", (S.size()-ry[i])-rx[i]);
        }
    }
    return 0;
}