P5829

buxiangzuola

#include<bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
typedef long long ll;
typedef unsigned long long ull;
template<typename T> inline T rd(T& x)
{
	T f=1;x=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(T)(c-'0');
	x*=f;
	return x;
}
ll rd(){ll x;rd(x);return x;}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
const int inf=1<<30;
const int N=1000005;
int fa[N][22],n,m,dep[N];char s[N];
int main()
{
	scanf("%s",s+1);n=strlen(s+1);
	fa[0][0]=fa[1][0]=0,dep[0]=0,dep[1]=1;
	for(register 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,dep[i]=dep[j]+1;
	}
	F(i,1,21) F(j,1,n) fa[j][i]=fa[fa[j][i-1]][i-1];
	rd(m);
	while(m--)
	{
		int x,y;rd(x);rd(y);if(dep[x]<dep[y]) swap(x,y);
		UF(i,21,0) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
		UF(i,21,0) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
		printf("%d\n",fa[x][0]);
	}
	return 0;
}