后缀树

众所周知：后缀树是不对劲的 Tire 树….

后缀树即是路径压缩之后的后缀 Trie ，满足其中的 一些节点 可以双射原串的所有后缀。
其分为 显示构造 与 隐式构造 两种，区别在于是否在字符串尾添加一个终止符。其中，显示构造的后缀树满足每个叶子双射原串的一个后缀。

众所周知，SAM 的 Parent 树是反串的后缀树，从而可以通过将字符串倒着插入 SAM 来得到一个串的后缀树。注意，这样得到的后缀树是隐式构造的。

后缀树为我们提供了一个新的思路：两个字符串的 LCP 是它们在 Trie 上的 LCA ，则两个后缀的 LCP 也是它们在后缀树上的 LCA。这可以被形式化地表达如下：

$$ \text{LCP}(s[i:n], s[j:n]) = \text{len}[ \text{LCA}(i, j) ] $$

其中等号后面的 $i, j$ 应当对应为在树上的编号，$\text{len}[]$ 即为 SAM 中的 len[] 数组。

给出一份查询两个后缀的 LCP 的代码。显然，该份代码也可以通过 SA 实现。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
using namespace std;

const int CN = 1e5 + 5;

int read(){
    int s = 0,ne = 1; char c = getchar();
    while(c < '0' || c > '9') ne = c == '-' ? -1 : 1, c = getchar();
    while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar();
    return s * ne;
}

class SAM{
  public: int len[CN << 1], nxt[CN << 1], son[CN << 1][26], lst, idx; 
    SAM() {nxt[0] = -1, idx = lst = 0;}
    int et(int c){
        int u = ++idx, p = lst;
        len[u] = len[p] + 1, lst = u;
        while(p ^ -1 && !son[p][c]) son[p][c] = u, p = nxt[p];
        if(p == -1) return idx;
        int d = son[p][c];
        if(len[d] == len[p] + 1) return nxt[u] = d, idx;
        int v = ++idx;
        nxt[v] = nxt[d], nxt[d] = nxt[u] = v, len[v] = len[p] + 1, memcpy(son[v], son[d], sizeof(son[d]));
        while(p ^ -1 && son[p][c] == d) son[p][c] = v, p = nxt[p];
        return idx - 1;
    }
} D;

int n, id[CN]; char ch[CN];

vector<int> to[CN];
void rbd(){
    for(int i = 1; i <= D.idx; i++) to[ D.nxt[i] ].push_back(i);
}

int fa[CN][30], dep[CN];
void dfs(int u, int p){
    fa[u][0] = p, dep[u] = dep[p] + 1; int sz = to[u].size();
    for(int i = 0; i < sz; i++){
        int v = to[u][i];
        if(v ^ p) dfs(v, u);
    }
}
int lca(int u, int v){
    if(dep[u] < dep[v]) swap(u, v);
    for(int k = 20; k + 1; k--) if(dep[ fa[u][k] ] >= dep[v]) u = fa[u][k];
    if(u ^ v) {for(int k = 20; k + 1; k--) if(fa[u][k] ^ fa[v][k]) u = fa[u][k], v = fa[v][k]; u = fa[u][0];}
    return u;
}

int main()
{
    freopen("_in.in", "r", stdin);

    cin >> ch; n = strlen(ch);
    for(int i = n - 1; i + 1; i--) id[i + 1] = D.et( ch[i] - 'a' );

    rbd(), dfs(0, 0);
    for(int k = 1; k <= 20; k++)
        for(int i = 1; i <= D.idx; i++)
            fa[i][k] = fa[ fa[i][k - 1] ][k - 1];
    
    int q = read();
    while(q--){
        int i = read(), j = read(), l = lca( id[i], id[j] );
        printf("%d", D.len[l]), puts("");
    }
}