我的思路是先运用 KMP 中的思想，预处理出 $nxt$ 数组（$Border$），并让 $i$ 向 $\large nxt_{i}$ 连边，记录深度，每次询问用倍增求 LCA，但一直 $17 \sim 25$ 测试点 WA，大佬能否前来敲打敲打

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <stack>
#include <map>
#define REP(i, x, y) for(int i = x; i < y; i++)
#define rep(i, x, y) for(int i = x; i <= y; i++)
#define PER(i, x, y) for(int i = x; i > y; i--)
#define per(i, x, y) for(int i = x; i >= y; i--)
#define lc (k << 1)
#define rc (k << 1 | 1)
using namespace std;
const int N = 1E6 + 5;
string s;
int len, m;
int fa[N][25];
int nxt[N], dep[N];
int lca(int x, int y)
{
	if(dep[x] < dep[y]) swap(x, y);
	int temp = dep[x] - dep[y];
	per(i, 22, 0)
	{
		if((temp >> i) & 1)
		{
			x = fa[x][i];
		}
	}
//	if(x == y) return fa[x][0];
	per(i, 22, 0)
	{
		if(fa[x][i] != fa[y][i])
		{
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return fa[x][0];
}
int main()
{
	cin >> s;
	len = s.length();
	s = "0" + s;
	nxt[0] = 0;
	nxt[1] = 0;
	fa[0][0] = 0;
	dep[0] = 0;
	fa[1][0] = 0;
	dep[1] = 1;
	int j = 0;
	for(int i = 2; i <= len; i++)
	{
		if(j && s[i] != s[j + 1])
		{
			j = nxt[j];
		}
		if(s[i] == s[j + 1])
		{
			j++;
		}
		nxt[i] = j;
		fa[i][0] = j;
		dep[i] = dep[j] + 1;
	}
	for(j = 1; j <= 22; j++)
	{
		for(int i = 1; i <= len; i++)
		{
			fa[i][j] = fa[fa[i][j - 1]][j - 1];
		}
	}
	scanf("%d", &m);
	while(m--)
	{
		int x, y;
		scanf("%d%d", &x, &y);
	    printf("%d\n", lca(x, y));
    }
	return 0;
}