题解 P4600 【[HEOI2012]旅行问题】

· · 题解

为啥感觉另一篇题解就约等于啥都没写啊

总结一下思考过程。首先根据“前缀”和“多串”，可知需要一个可以接收许多串的自动机，比如线段树合并维护反串的广义SAMAC自动机，而字典树正好是前缀树，于是考虑在AC自动机上搞事情。

考虑fail数组的意义，由于AC自动机本身的前缀性质，不需要匹配前缀，所以fail会指向与自己相同且深度较浅的后缀。然后就考虑搞一个vector出来维护每个串的每个前缀的节点编号，由于深度期望越大，求fail时跳的次数期望越少，所以求一下LCA就是最长后缀了。

然后是代码，一A就很开心.jpg

据说卡倍增，然而都9102年了为什么不树剖？

#define Sigma 27
#define MAXN 1000010
#define Mod 1000000007

using namespace std ;

char S[MAXN] ;
int T, M, L[MAXN] ;
vector <int> pre[MAXN] ;
struct Edge{
    int to, next ;
    #define p_b push_back
    #define to(k) E[k].to
    #define next(k) E[k].next
}E[MAXN] ; int head[MAXN], cnt ;
int sze[MAXN], dep[MAXN], fa[MAXN], top[MAXN], son[MAXN] ;

void add(int u, int v){
    E[++ cnt].to = v, E[cnt].next = head[u], head[u] = cnt ;
}
struct ACAM{
    queue <int> q ;
    int sz, fail[MAXN] ;
    int trie[MAXN][Sigma], ans[MAXN] ;
    void insert(char *s, int n){
        int rt = 0, x ; pre[n].p_b(0) ;
        for (int i = 1 ; i <= L[n] ; ++ i){
            x = s[i] - 'a' ;
            if (!trie[rt][x])
                trie[rt][x] = ++ sz,
                ans[trie[rt][x]] = (26ll * ans[rt] + x) % Mod ;
            pre[n].p_b(trie[rt][x]) ; rt = trie[rt][x] ;
        }
    }
    void build(){
        for (int i = 0 ; i < Sigma ; ++ i)
            if (trie[0][i]) q.push(trie[0][i]) ;
        while (!q.empty()){
            int n = q.front() ; add(fail[n], n), q.pop() ;
//            cout << n << endl ;
            for (int i = 0 ; i < 26 ; ++ i){
                if (!trie[n][i]) trie[n][i] = trie[fail[n]][i] ;
                else fail[trie[n][i]] = trie[fail[n]][i], q.push(trie[n][i]) ;
            }
        }
    }
}AC ;
void dfs(int u){
    sze[u] = 1, dep[u] = dep[fa[u]] + 1 ;
    for (int k = head[u] ; k ; k = next(k)){
        fa[to(k)] = u, dfs(to(k)), sze[u] += sze[to(k)] ;
        if (!son[u] || sze[to(k)] > sze[son[u]]) son[u] = to(k) ;
    }
}
void dfs2(int u, int tp){
    top[u] = tp ;
    if (son[u]) dfs2(son[u], tp) ;
    for (int k = head[u] ; k ; k = next(k))
        if (to(k) != son[u]) dfs2(to(k), to(k)) ;
}
int lca(int u, int v){
    // qw(u, '\n', true), qw(v, '\n', true) ;
    // cout << u << " " << v << endl ;
    while (top[u] != top[v]){
        if (dep[top[u]] >= dep[top[v]]) u = fa[top[u]] ;
        else v = fa[top[v]] ;
    }
    return dep[u] < dep[v] ? u : v ;
}
int qr(){
    int r = 0 ; char c = getchar() ;
    while (!isdigit(c)) c = getchar() ;
    while (isdigit(c)) r = (r << 1) + (r << 3) + c - 48, c = getchar() ;
    return r ;
}
int main(){
    cin >> T ;
    for (int i = 1 ; i <= T ; ++ i)
        scanf("%s", S + 1), L[i] = strlen(S + 1), AC.insert(S, i) ;
    AC.build() ; cin >> M ; dfs(0), dfs2(0, 0) ;
     int p, l, q, r, x, y ;
    while (M --){
        p = qr(), l = qr(), q = qr(), r = qr() ;
        x = pre[p][l], y = pre[q][r], printf("%d\n", AC.ans[lca(x, y)]) ;
    }
}