思路：
考虑对字符串\(s\)来说，假设\(s‘ = s_{1...x}\)是字符串的一个\(border\)，同时\(s‘‘ = s‘_{1...y}\)是\(s‘\)的一个border，那么\(s‘‘\)也一定是\(s\)的一个长度更小的\(border\)，即字符串\(s\)的\(border\)的\(border\)也是\(s\)的一个\(border\)。

这样我们就可从小遍历让每个位置\(i\)的\(border_i\)都连一条指向\(i\)的边，这样我们就可以构造出一棵\(border\)树，满足对于任意一个节点一定处在它的任何一个\(border\)的子树中。

考虑如何构建失配树，即每个点的\(fail\)指针改指向何处，假设在当前位置出现了和前缀的失配，那就\(while\)寻找直到与当前这个位置匹配的或者指向0再停下来，所以\(j\)指向的是当前当已经匹配成功的位置或者是从\(0\)开始，所以判断用的是\(j+1\)

再考虑最长公共\(border\)，失配树构建出来后，我们可以发现，深度约大的节点的值也是越大的(即代表它代表的\(border\)越长)，所以问题可以转换为失配树上的两个节点求一个深度最大的公共祖先，即最近公共祖先\(LCA\)，所以倍增求一下即可。

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define eb emplace_back
#define MP make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define lson rt<<1
#define rson rt<<1|1
#define CLOSE std::ios::sync_with_stdio(false)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-6;
//border树 新科技
const int N = 1e6 + 10;
char s[N];
int nex[N],fa[N][25],n,dep[N],m;
int lca(int x,int y) {
	if(dep[x] < dep[y]) swap(x,y);
	for(int i = 20;i >= 0;i --) if(dep[fa[x][i]] >= dep[y]) x = fa[x][i];
	for(int i = 20;i >= 0;i --) {
		if(fa[x][i] != fa[y][i]) {
			x = fa[x][i],y = fa[y][i];
		}
	}
	return fa[x][0];
}
void solve() {
	scanf("%s",s+1);
	n = strlen(s+1);
	fa[0][0] = 0,fa[1][0] = 0,dep[0] = 0,dep[1] = 1;
	for(int i = 2,j = 0;i <= n;i ++) {//求抱含当前这一位的最长的前后缀
		while(j != 0 && s[j+1] != s[i]) j = fa[j][0]; //即将匹配的下一个字符仍不相等
		if(s[j+1] == s[i]) ++j;
		fa[i][0] = j;//即失配指针 fail
		dep[i] = dep[j] + 1;
	}

	for(int i = 1;i <= n;i ++) {
		for(int j = 1;j <= 22;j ++) {
			fa[i][j] = fa[fa[i][j-1]][j-1];
		}
	}

	scanf("%d",&m);
	int p,q;
	while(m--) {
		scanf("%d%d",&p,&q);
		printf("%d\n",lca(p,q));
	}
}

int main() {
	solve();
	return 0;
}

P5829 【模板】失配树 border