Description：

一个小写字母字符串 $S$ ， $q$ 次询问每次给出 $l,r$ ，求 $s[l\dots r]$ 的 $Border$ 。

$1\leqslant |S|\leqslant 2\times 10^5$

Solution：

首先肯定是先建出后缀自动机，然后在后缀自动机上做。

发现实际让我们求的就是满足 $i - l + 1\leqslant \text{lcp}(i,r),i<r$ 的最大的 $i$ ，先考虑一个暴力的做法，由于 $border$ 一定是 $s[l:r]$ 的一个后缀，所以就从后缀自动机 $r$ 对应的节点暴力向上跳，同时判断是否有解，这个判断过程可以用线段树合并维护 $right$ 集合，实际上就是一个查询合法的区间（ $i<\min(r,\text{lcp}(i,r)+l)$ ）的最大值的问题。

考虑优化这个问题的求解，我们对整棵树进行轻重链剖分，然后会发现每个询问被拆成了从 $r$ 对应节点到根的不超过 $\log$ 个重链的前缀，那么我们考虑对这 $\log$ 个片段分别求解，最后合并答案。

首先我们知道 $\text{lcp}(i,r)=SAM[lca(s[i],s[r])].maxl$ ，那么我们从 $s[r]$ 往上跳重链，如果 $x$ 是一个重链的前缀的最后一个节点，那么 $x$ 作为 $lca(s[i],s[r])$ 的话 $i$ 一定来自重链的后面那部分或者这个点的其他轻儿子，只是不包括 $s[r]$ 所在的轻子树，但是由于 $maxl$ 是沿深度递增的，所以即使来自 $s[r]$ 所在子树也没有关系，因为在上一个位置决策区间是包含这个点的决策区间的，所以可以直接用最开始那个暴力线段树合并维护 $right$ 集合区间最大值离线回答询问来解决。

然后再考虑是一个前缀的非最后节点的情况，还是把询问离线，把条件改写成 $i-\text{lcp(i,r)}<l$ ，然后使用树上启发式合并的技巧，我们当 $dfs$ 到一个重链时，先 $dfs$ 处理和这个重链有关的所有重链的答案，然后从上到下枚举重链上的点，暴力 $dfs$ 进轻子树并暴力插入到这个重链的线段树中，由树上启发式合并可以知道这个复杂度是对的。但是这里又有一个问题，就是我们实际上查询的是满足 $i-\text{lcp}(i,r)<l$ 并且 $i<r$ 的 $i$ 的最大值，看上去需要二维数据结构解决，但是实际上是不用的，因为这个题有个特点是下标就是答案，也就是说下标越大答案就越大，于是我们就可以在线段树上二分，具体做法是可以在线段树上维护 $i-\text{lcp}(i,r)$ 的区间最小值，如果右区间的最小值都太大的话，那么我们就只好进入左区间查询，否则先去右区间查询一下看能不能找到，如果找不到还去左区间。

总复杂度 $O(n\log^2n)$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int n;

#define MAXN 400010

char c[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN];

int edgenum = 0;

int lin[MAXN] = {0};

inline void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	return;

}

namespace SAM

{

	struct node

	{

		int tr[26];

		int par,maxl;

	}s[MAXN];

	int ptr = 1,root = 1,last = 1;

	inline int newnode(int l){int k = ++ptr;s[k].maxl = l;return k;}

	int pos[MAXN],id[MAXN];

	inline void extend(int k,int i)

	{

		register int p = last;

		register int np = newnode(s[p].maxl + 1);

		id[np] = i;

		pos[i] = np;

		for(;p && s[p].tr[k] == 0;p = s[p].par)s[p].tr[k] = np;

		if(p == 0)s[np].par = root;

		else

		{

			register int q = s[p].tr[k];

			if(s[p].maxl + 1 == s[q].maxl)s[np].par = q;

			else

			{

				register int nq = newnode(s[p].maxl + 1);

				memcpy(s[nq].tr,s[q].tr,sizeof(s[q].tr));

				s[nq].par = s[q].par;

				s[q].par = s[np].par = nq;

				for(;p && s[p].tr[k] == q;p = s[p].par)s[p].tr[k] = nq;

			}

		}

		last = np;

		return;

	}

	inline void build()

	{

		for(register int i = 2;i <= ptr;++i)add(s[i].par,i);

		return;

	}

}

int fa[MAXN],dep[MAXN],siz[MAXN],son[MAXN],top[MAXN];

void dfs1(int k,int depth)

{

	siz[k] = 1;dep[k] = depth;

	for(register int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa[k])continue;

		fa[e[i].to] = k;

		dfs1(e[i].to,depth + 1);

		siz[k] += siz[e[i].to];

		if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

		{

			son[k] = e[i].to;

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	top[k] = tp;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(register int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != son[k] && e[i].to != fa[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

int m;

int ans[MAXN];

struct query

{

	int l,r;

}q[MAXN];

namespace work1

{

	vector<int> v[MAXN];

	inline void add(int pos,int id)

	{

		v[pos].push_back(id);

		return;

	}

	struct node

	{

		int lc,rc;

		int maxv;

	}t[MAXN * 30];

	int ptr = 0;

	inline int newnode(){return ++ptr;}

	int root[MAXN];

	#define mid ((l + r) >> 1)

	void insert(int &rt,int p,int l,int r)

	{

		if(rt == 0)rt = newnode();

		if(l == r)

		{

			t[rt].maxv = p;

			return;

		}

		if(p <= mid)insert(t[rt].lc,p,l,mid);

		else insert(t[rt].rc,p,mid + 1,r);

		t[rt].maxv = max(t[t[rt].lc].maxv,t[t[rt].rc].maxv);

		return;

	}

	int merge(int x,int y)

	{

		if(x == 0 || y == 0)return x + y;

		t[x].lc = merge(t[x].lc,t[y].lc);

		t[x].rc = merge(t[x].rc,t[y].rc);

		t[x].maxv = max(t[t[x].lc].maxv,t[t[x].rc].maxv);

		return x;

	}

	int query(int rt,int L,int R,int l,int r)

	{

		if(rt == 0)return 0;

		if(L <= l && r <= R)return t[rt].maxv;

		register int res = 0;

		if(L <= mid)res = max(res,query(t[rt].lc,L,R,l,mid));

		if(R > mid)res = max(res,query(t[rt].rc,L,R,mid + 1,r));

		return res;

	}

	void dfs(int k)

	{

		for(register int i = lin[k];i != 0;i = e[i].nxt)

		{

			dfs(e[i].to);

			root[k] = merge(root[k],root[e[i].to]);

		}

		for(register vector<int>::iterator it = v[k].begin();it != v[k].end();++it)

		{

			ans[*it] = max(ans[*it],query(root[k],1,min(q[*it].r,SAM::s[k].maxl + q[*it].l) - 1,1,n));

		}

		return;

	}

	inline void solve()

	{

		for(register int i = 1;i <= n;++i)insert(root[SAM::pos[i]],i,1,n);

		dfs(1);

		return;

	}

}

namespace work2

{

	vector<int> v[MAXN];

	inline void add(int pos,int id)

	{

		v[pos].push_back(id);

		return;

	}

	struct node

	{

		int lc,rc;

		int minv;

		node(){minv = 0x3f3f3f3f;}

	}t[MAXN * 30];

	int ptr = 0;

	inline int newnode(){int k = ++ptr;t[k].lc = t[k].rc = 0;return k;}

	int root;

	void insert(int &rt,int p,int k,int l,int r)

	{

		if(rt == 0)rt = newnode();

		if(l == r)

		{

			t[rt].minv = k;

			return;

		}

		if(p <= mid)insert(t[rt].lc,p,k,l,mid);

		else insert(t[rt].rc,p,k,mid + 1,r);

		t[rt].minv = min(t[t[rt].lc].minv,t[t[rt].rc].minv);

		return;

	}

	int query(int rt,int L,int R,int lim,int l,int r)

	{

		if(rt == 0)return 0;

		if(t[rt].minv > lim)return 0;

		if(l == r)return l;

		if(L <= l && r <= R)

		{

			if(t[rt].rc != 0 && t[t[rt].rc].minv <= lim)return query(t[rt].rc,L,R,lim,mid + 1,r);

			else if(t[rt].lc != 0 && t[t[rt].lc].minv <= lim)return query(t[rt].lc,L,R,lim,l,mid);

			else return 0;

		}

		register int res = 0;

		if(R > mid && t[rt].rc != 0 && t[t[rt].rc].minv <= lim)res = query(t[rt].rc,L,R,lim,mid + 1,r);

		if(res != 0)return res;

		else if(L <= mid && t[rt].lc != 0 && t[t[rt].lc].minv <= lim)return query(t[rt].lc,L,R,lim,l,mid);

		else return 0;

	}

	void getval(int k,int lca)

	{

		if(SAM::id[k])insert(root,SAM::id[k],SAM::id[k] - SAM::s[lca].maxl,1,n);

		for(register int i = lin[k];i != 0;i = e[i].nxt)

		{

			getval(e[i].to,lca);

		}

		return;

	}

	void dfs(int k)

	{

		for(register int p = k;p;p = son[p])

		{

			for(register int i = lin[p];i != 0;i = e[i].nxt)

			{

				if(e[i].to == son[p])continue;

				dfs(e[i].to);

			}

		}

		root = ptr = 0;

		for(register int p = k;p;p = son[p])

		{

			for(register vector<int>::iterator it = v[p].begin();it != v[p].end();++it)

			{

				ans[*it] = max(ans[*it],query(root,q[*it].l,q[*it].r - 1,q[*it].l - 1,1,n));

			}

			for(register int i = lin[p];i != 0;i = e[i].nxt)

			{

				if(e[i].to != son[p])getval(e[i].to,p);

			}

			if(SAM::id[p])insert(root,SAM::id[p],SAM::id[p] - SAM::s[p].maxl,1,n);

		}

		return;

	}

	void solve()

	{

		dfs(1);

		return;

	}

}

int main()

{

	scanf("%s",c + 1);

	n = strlen(c + 1);

	for(register int i = 1;i <= n;++i)SAM::extend(c[i] - 'a',i);

	SAM::build();

	dfs1(1,1);dfs2(1,1);

	scanf("%d",&m);

	for(register int i = 1;i <= m;++i)

	{

		q[i].l = rd();q[i].r = rd();

		for(register int cur = SAM::pos[q[i].r];cur != 0;cur = fa[top[cur]])

		{

			work1::add(cur,i);work2::add(cur,i);

		}

	}

	work1::solve();

	work2::solve();

	for(int i = 1;i <= m;++i)printf("%d\n",max(ans[i] - q[i].l + 1,0)); 

	return 0;

}