题解 P4600 【[HEOI2012]旅行问题】
皎月半洒花
2019-12-19 16:25:08
~~为啥感觉另一篇题解就约等于啥都没写啊~~
总结一下思考过程。首先根据“前缀”和“多串”，可知需要一个可以接收许多串的自动机，比如~~线段树合并维护反串的广义SAM~~AC自动机，而字典树正好是前缀树，于是考虑在AC自动机上搞事情。
考虑`fail`数组的意义，由于AC自动机本身的前缀性质，不需要匹配前缀，所以`fail`会指向与自己相同且深度较浅的后缀。然后就考虑搞一个`vector`出来维护每个串的每个前缀的节点编号，由于深度期望越大，求`fail`时跳的次数期望越少，所以求一下`LCA`就是最长后缀了。
然后是代码，一A就很开心.jpg
据说卡倍增，然而都9102年了为什么不树剖？
```cpp
#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)]) ;
}
}
```