【冲刺NOI】字符串专训

一堆并不养生的字符串题。

尽管SAM很短，但还是能把手敲烂。

因为很多道题都是SAM+树上线段树合并，这里就只讲一道稍微难点的。

首先考虑贪心简化问题，因为只要求前一个串出现两次，所以只有一种连法是最优的，就是前一个串是后一个串的最长border。

我们把SAM的 p a r e n t   t r e e rm parent,tree parenttree 建出来，考虑答案序列的最后一个子串，把它换成它所在 p a r e n t   t r e e rm parent,tree parenttree 上的节点上的最长串一定是不劣的，另外根据这个 e n d   p o s rm end,pos endpos 的性质，一个节点最长串的最长border一定也是某个祖先节点的最长串。

所以我们用线段树合并配合建出这些到最长border的边，然后把所有节点拉下来跑拓扑排序即可。

#include//JZM yyds!!
#define ll long long//God JZM!!
#define lll __int128//JZM RollInDark!!
#define uns unsigned
#define fi first
#define se second
#define IF (it->fi)
#define IS (it->se)
#define lowbit(x) ((x)&-(x))
#define END putchar('n')
#define inline jzmyyds
using namespace std;
const int MAXN=4e5+5;
const ll INF=1e18;
ll read(){
	ll x=0;bool f=1;char s=getchar();
	while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return f?x:-x;
}
int ptf[50],lpt;
void print(ll x,char c='n'){
	if(x<0)putchar('-'),x=-x;
	ptf[lpt=1]=x%10;
	while(x>9)x/=10,ptf[++lpt]=x%10;
	while(lpt)putchar(ptf[lpt--]^48);
	if(c>0)putchar(c);
}
struct itn{
	int ls,rs;
}t[MAXN<<6];
int IN,rt[MAXN<<1];
int add(int x,int l,int r,int z){
	if(!x)x=++IN;
	if(l==r)return x;
	int mid=(l+r)>>1;
	if(z<=mid)t[x].ls=add(t[x].ls,l,mid,z);
	else t[x].rs=add(t[x].rs,mid+1,r,z);
	return x;
}
int merg(int x,int y,int l,int r){
	if(!x||!y)return x^y;
	if(l==r)return x;
	int mid=(l+r)>>1,res=++IN;
	t[res].ls=merg(t[x].ls,t[y].ls,l,mid);
	t[res].rs=merg(t[x].rs,t[y].rs,mid+1,r);
	return res;
}
int A,B;
bool query(int x,int l,int r){
	if(!x||A>B)return 0;
	if(l>=A&&r<=B)return 1;
	int mid=(l+r)>>1;bool res=0;
	if(A<=mid)res|=query(t[x].ls,l,mid);
	if(!res&&B>mid)res|=query(t[x].rs,mid+1,r);
	return res;
}
int n,m,du[MAXN],dp[MAXN],ans;
char s[MAXN];
struct SAM{
	int ch[26],fa,len;
}sam[MAXN];
int las=1,tot=1,bg[MAXN];
int samadd(int c){
	int p=las,np=las=++tot;sam[np].len=sam[p].len+1;
	for(;p&&!sam[p].ch[c];p=sam[p].fa)sam[p].ch[c]=np;
	if(!p)sam[np].fa=1;
	else{int q=sam[p].ch[c],nq;
		if(sam[q].len==sam[p].len+1)sam[np].fa=q;
		else{
			nq=++tot,sam[nq]=sam[q],sam[nq].len=sam[p].len+1;
			sam[q].fa=sam[np].fa=nq;
			for(;p&&sam[p].ch[c]==q;p=sam[p].fa)sam[p].ch[c]=nq;
		}
	}return np;
}
int id[MAXN],fa[MAXN][23];
queueq;
vectorG[MAXN],D[MAXN];
void pdfs(int x){
	fa[x][0]=sam[x].fa;
	for(int i=1;i<=19;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
	for(int v:G[x])
		pdfs(v),bg[x]=max(bg[x],bg[v]),rt[x]=merg(rt[x],rt[v],1,n);
}
void doit(int x){
	int to=x;
	for(int i=19;i>=0;i--)if(fa[to][i]){
		int y=fa[to][i];
		A=bg[x]-sam[x].len+sam[y].len,B=bg[x]-1;
		if(!query(rt[y],1,n))to=y;
	}if(to>1)to=sam[to].fa;
	if(to>1)D[to].push_back(x),du[x]++;
}
int main()
{
	n=read(),*new(int)=scanf("%s",s+1);
	for(int i=1;i<=n;i++)
		id[i]=samadd(s[i]-'a'),rt[id[i]]=add(rt[id[i]],1,n,i),bg[id[i]]=i;
	for(int i=2;i<=tot;i++)G[sam[i].fa].push_back(i);
	pdfs(1);
	for(int i=2;i<=tot;i++)doit(i);
	for(int i=2;i<=tot;i++)if(!du[i])q.push(i);
	while(!q.empty()){
		int u=q.front();
		q.pop(),ans=max(ans,dp[u]+1);
		for(int v:D[u]){
			du[v]--,dp[v]=max(dp[v],dp[u]+1);
			if(!du[v])q.push(v);
		}
	}
	print(ans);
	return 0;
}

考虑重链剖分，把路径拆成 log ⁡ n log n logn 条 d f s dfs dfs 序连续的段，然后把两条路径的段按顺序对齐再切一下，变成长度相等的 2 log ⁡ n 2log n 2logn 对连续段，然后就可以直接扫过去用哈希判断匹配了。

失配的那一段要打一个小二分，总共复杂度是 O ( m log ⁡ n ) O(mlog n) O(mlogn)。

#include//JZM yyds!!
#define ll long long//God JZM!!
#define lll __int128//JZM RollInDark!!
#define uns unsigned
#define fi first
#define se second
#define IF (it->fi)
#define IS (it->se)
#define lowbit(x) ((x)&-(x))
#define END putchar('n')
#define inline jzmyyds
using namespace std;
const int MAXN=3e5+5;
const ll INF=1e18;
ll read(){
	ll x=0;bool f=1;char s=getchar();
	while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return f?x:-x;
}
int ptf[50],lpt;
void print(ll x,char c='n'){
	if(x<0)putchar('-'),x=-x;
	ptf[lpt=1]=x%10;
	while(x>9)x/=10,ptf[++lpt]=x%10;
	while(lpt)putchar(ptf[lpt--]^48);
	if(c>0)putchar(c);
}
const ll MOD=998244853,cg=29;
ll ksm(ll a,ll b,ll mo){
	ll res=1;
	for(;b;b>>=1,a=a*a%mo)if(b&1)res=res*a%mo;
	return res;
}
#define pii pair
ll mi[MAXN],vi[MAXN],f[MAXN],g[MAXN];
char in[MAXN];
int n,a[MAXN],fa[MAXN],dep[MAXN],hs[MAXN],siz[MAXN];
int hd[MAXN],tl[MAXN],id[MAXN],tp[MAXN],IN;
vectorG[MAXN];
void pdfs(int x){
	siz[x]=1,dep[x]=dep[fa[x]]+1,g[x]=(g[fa[x]]*cg+a[x])%MOD;
	f[x]=(f[fa[x]]+a[x]*mi[dep[x]-1])%MOD;
	for(int v:G[x])if(v^fa[x]){
		fa[v]=x,pdfs(v),siz[x]+=siz[v];
		if(siz[v]>siz[hs[x]])hs[x]=v;
	}
}
void dfs(int x){
	hd[x]=++IN,id[IN]=x,tp[x]=(x==hs[fa[x]]?tp[fa[x]]:x);
	if(hs[x])dfs(hs[x]);
	for(int v:G[x])if((v^fa[x])&&(v^hs[x]))dfs(v);
	tl[x]=IN;
}
ll HS(int u,int v){
	if(dep[u]>=dep[v])return (f[u]-f[fa[v]]+MOD)*vi[dep[v]-1]%MOD;
	else return (g[v]-g[fa[u]]*mi[dep[v]-dep[u]+1]%MOD+MOD)%MOD;
}
int lth(const pii&x){
	return dep[x.fi]>dep[x.se]?dep[x.fi]-dep[x.se]+1:dep[x.se]-dep[x.fi]+1;
}
int gmid(int u,int v,int k){
	if(dep[u]A,B,C,D;
void getlr(int u,int v,vector&A){
	while(tp[u]^tp[v]){
		if(dep[tp[u]]>=dep[tp[v]])
			A.emplace_back(pii(u,tp[u])),u=fa[tp[u]];
		else st[++le]=pii(tp[v],v),v=fa[tp[v]];
	}A.emplace_back(pii(u,v));
	while(le)A.push_back(st[le--]);
}
int main()
{
	n=read();
	*new(int)=scanf("%s",in+1);
	for(int i=1;i<=n;i++)a[i]=in[i]-'a';
	mi[0]=1,vi[0]=1,vi[1]=ksm(cg,MOD-2,MOD);
	for(int i=1;i<=n;i++)mi[i]=mi[i-1]*cg%MOD,vi[i]=vi[i-1]*vi[1]%MOD;
	for(int i=1,u,v;i
		int a=read(),b=read(),c=read(),d=read(),ans=0;
		A.clear(),B.clear(),C.clear(),D.clear();
		getlr(a,b,C),getlr(c,d,D);
		for(int i=0,j=0,lmi=C.size(),lmj=D.size();;){
			if(i>=lmi&&j>=lmj)break;
			if(j>=lmj)A.push_back(C[i]),i++;
			else if(i>=lmi)B.push_back(D[j]),j++;
			else{
				int li=lth(C[i]),lj=lth(D[j]);
				if(li
					B.emplace_back(pii(D[j].fi,gmid(D[j].fi,D[j].se,li)));
					A.push_back(C[i]),D[j].fi=gmid(D[j].fi,D[j].se,li+1),i++;
				}else if(li>lj){
					A.emplace_back(pii(C[i].fi,gmid(C[i].fi,C[i].se,lj)));
					B.push_back(D[j]),C[i].fi=gmid(C[i].fi,C[i].se,lj+1),j++;
				}else A.push_back(C[i]),B.push_back(D[j]),i++,j++;
			}
		}
		reverse(A.begin(),A.end()),reverse(B.begin(),B.end());
		while(!A.empty()&&!B.empty()){
			int u=A.back().fi,u_=A.back().se,v=B.back().fi,v_=B.back().se;
			if(HS(u,u_)==HS(v,v_))ans+=lth(A.back()),A.pop_back(),B.pop_back();
			else{
				int l=0,r=lth(A.back()),mid=2333;
				while(l
					mid=(l+r+1)>>1;
					if(HS(u,gmid(u,u_,mid))==HS(v,gmid(v,v_,mid)))l=mid;
					else r=mid-1;
				}ans+=l;break;
			}
		}
		print(ans);
	}
	return 0;
}

操作成全为 a 或全为 b，其实就是使得两个串内都不存在不合法位置，即相邻两个字符不同的位置。首先我们如果操作的位置在两个相同字符的中间肯定不优，所以我们只操作不合法位置。

设 f ( a ) f(a) f(a) 表示字符串 a a a 中不合法位置个数，那么可以想到一种贪心+双指针的做法，操作次数为 max ⁡ ( f ( s ) , f ( t ) ) + [ f ( s ) = = f ( t ) & & s 1 = = t 1 ] max(f(s),f(t))+[f(s)==f(t)&&s_1==t_1] max(f(s),f(t))+[f(s)==f(t)&&s1​==t1​]，这是可以很快算出来的。

注意到一次操作最多减少2个不合法位置，所以我们需要让操作次数尽可能接近 f ( s ) + f ( t ) 2 frac{f(s)+f(t)}{2} 2f(s)+f(t)​。

可以想到先进行一次操作，使不合法位置多的那边转移到少的那边，那么就可以把 max ⁡ ( f ( s ) , f ( t ) ) max(f(s),f(t)) max(f(s),f(t)) 几乎变为 f ( s ) + f ( t ) 2 frac{f(s)+f(t)}{2} 2f(s)+f(t)​。

我们可以枚举第一次操作的位置并 O ( 1 ) O(1) O(1) 计算操作次数，选出操作次数最少的方案，然后用双指针模拟。注意到有用的位置只有一个串的不合法位置和另一个串的不合法位置中的前面几个、中间几个、最后几个，所以枚举的数量是 O ( n ) O(n) O(n) 的。

#include//JZM yyds!!
#define ll long long//God JZM!!
#define lll __int128//JZM RollInDark!!
#define uns unsigned
#define fi first
#define se second
#define IF (it->fi)
#define IS (it->se)
#define lowbit(x) ((x)&-(x))
#define END putchar('n')
#define inline jzmyyds
using namespace std;
const int MAXN=5e5+5;
const ll INF=1e18;
ll read(){
	ll x=0;bool f=1;char s=getchar();
	while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return f?x:-x;
}
int ptf[50],lpt;
void print(ll x,char c='n'){
	if(x<0)putchar('-'),x=-x;
	ptf[lpt=1]=x%10;
	while(x>9)x/=10,ptf[++lpt]=x%10;
	while(lpt)putchar(ptf[lpt--]^48);
	if(c>0)putchar(c);
}
int n,m,fc,fd;
string a,b;
char c,d;
#define pii pair
pii sd;
int mn,ta[MAXN],tb[MAXN];
vectoran1,an2;
int main()
{
	cin>>a>>b;
	for(int i=0,lim=a.length();i
		int l=(fd>>1),r=min(fd+1,l+4);
		if(i>=(fc>>1)&&i<=(fc>>1)+4)l=0,r=fd+1;
		for(int j=l;j<=r;j++){
			if(!j&&i>fc)continue;
			if(!i&&j>fd)continue;
			int f=fc-i+j-1,g=fd-j+i-1;
			if(!j||i>fc||(a[ta[i]]^b[tb[j]-1]))f++;
			if(!i||j>fd||(b[tb[j]]^a[ta[i]-1]))g++;
			char fa=!j?a[ta[i]]:b[0],fb=!i?b[tb[j]]:a[0];
			int cp=max(f,g)+1+(fa==fb&&f==g);
			if(cp0||sd.se>0)an1.push_back(sd),an2.push_back(sd);
	n=a.length(),m=b.length();
	c='a',d='b',fc=fd=0;
	for(int i=0,j=0;;){
		while(i0||fd>0)an1.emplace_back(pii(fc,fd));
		swap(c,d),swap(fc,fd);
	}c='b',d='a',fc=fd=0;
	for(int i=0,j=0;;){
		while(i0||fd>0)an2.emplace_back(pii(fc,fd));
		swap(c,d),swap(fc,fd);
	}
	if(an1.size()>an2.size())swap(an1,an2);
	print(an1.size());
	for(auto x:an1)print(x.fi,' '),print(x.se);
	return 0;
}

题意：定义字符串的排名顺序是短的串在前，长度相同的按字典序排。Q次询问求字符串的排名第k子串。

我们倒着建立SAM，然后把 p a r e n t   t r e e rm parent,tree parenttree 上每个节点的儿子排个序，那么子串的字典序就等价于在这棵树上的dfs序了。

我们可以从小到达枚举长度 i i i，按dfs序维护串长包含 i i i 的节点，然后询问直接按 k 排序后指针扫+线段树二分即可。

#include//JZM yyds!!
#define ll long long//God JZM!!
#define lll __int128//JZM RollInDark!!
#define uns unsigned
#define fi first
#define se second
#define IF (it->fi)
#define IS (it->se)
#define lowbit(x) ((x)&-(x))
#define END putchar('n')
#define inline jzmyyds
using namespace std;
const int MAXN=1e6+6;
const ll INF=1e18;
ll read(){
	ll x=0;bool f=1;char s=getchar();
	while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return f?x:-x;
}
int ptf[50],lpt;
void print(ll x,char c='n'){
	if(x<0)putchar('-'),x=-x;
	ptf[lpt=1]=x%10;
	while(x>9)x/=10,ptf[++lpt]=x%10;
	while(lpt)putchar(ptf[lpt--]^48);
	if(c>0)putchar(c);
}
int n,m,sr[MAXN],L[MAXN],R[MAXN];
char s[MAXN];
struct SAM{
	int ch[26],fa,len;
}sam[MAXN<<1];
int las=1,tot=1,bg[MAXN<<1],fr[MAXN<<1];
int samadd(int c){
	int p=las,np=las=++tot;sam[np].len=sam[p].len+1;
	for(;p&&!sam[p].ch[c];p=sam[p].fa)sam[p].ch[c]=np;
	if(!p)sam[np].fa=1;
	else{int q=sam[p].ch[c],nq;
		if(sam[q].len==sam[p].len+1)sam[np].fa=q;
		else{
			nq=++tot,sam[nq]=sam[q],sam[nq].len=sam[p].len+1;
			sam[q].fa=sam[np].fa=nq;
			for(;p&&sam[p].ch[c]==q;p=sam[p].fa)sam[p].ch[c]=nq;
		}
	}return np;
}
vectorG[MAXN<<1];
int hd[MAXN<<1],id[MAXN<<1],IN;
void pdfs(int x){
	for(int v:G[x])pdfs(v),bg[x]=min(bg[x],bg[v]);
	fr[x]=s[bg[x]+sam[sam[x].fa].len]-'a';
	sort(G[x].begin(),G[x].end(),[](int a,int b){
		return fr[a]
	hd[x]=++IN,id[IN]=x;
	for(int v:G[x])dfs(v);
}
struct{//zkw
	int f[MAXN*6],p;
	void init(int n){for(p=1;pfor(x=p+x;x;x>>=1)f[x]+=d;}
	int sch(int k){//Binary Search on zkw
		int x=2;
		for(;xad[MAXN];
ll k[MAXN];
int main()
{
	*new(int)=scanf("%s",s+1),n=strlen(s+1);
	for(int i=(n<<1)+3;i>0;i--)bg[i]=n+1;
	for(int i=n;i>0;i--)bg[samadd(s[i]-'a')]=i;
	for(int i=2;i<=tot;i++)G[sam[i].fa].push_back(i);
	pdfs(1),dfs(1),T.init(IN);
	for(int i=2;i<=tot;i++)
		ad[sam[sam[i].fa].len+1].emplace_back(hd[i]<<2|2),
		ad[sam[i].len+1].emplace_back(hd[i]<<2);
	m=read();
	for(int i=1;i<=m;i++)k[i]=read(),sr[i]=i,L[i]=R[i]=-1;
	sort(sr+1,sr+1+m,[](int x,int y){return k[x]
		for(int x:ad[i])T.add(x>>2,(x&3)-1);
		while(j<=m&&k[sr[j]]<=d+T.f[1])
			L[sr[j]]=bg[id[T.sch(k[sr[j]]-d)]],R[sr[j]]=L[sr[j]]+i-1,j++;
		d+=T.f[1];
	}
	for(int i=1;i<=m;i++)print(L[i],' '),print(R[i]);
	return 0;
}

我们把两个串的字符交错合并成一个新串，那么相当于要求把这个新串划分成若干偶回文串，使得长度>2的偶回文串的个数最少。

可以想到建立回文自动机然后DP。每次转移需要枚举当前位置的每一个回文后缀，然而回文自动机上暴力跳 f a i l fail fail 的复杂度是 O ( n ) O(n) O(n) 的。

我们可以利用回文 b o r d e r border border 的性质：跳 f a i l fail fail 链中会遇到不超过 log ⁡ n log n logn 段连续的等差数列。我们若能对每一段等差数列直接求最优解，那么就是 O ( n log ⁡ n ) O(nlog n) O(nlogn)。

你可以使用一些数据结构，但是最简单的方法是直接在等差数列的开头记录最优解。因为建立 f a i l fail fail 链的过程中若某个等差数列变长，那么一定是在原来的若干个转移位置的后面新增了一个，把它记录即可。

具体过程看代码最好。

#include//JZM yyds!!
#define ll long long//God JZM!!
#define lll __int128//JZM RollInDark!!
#define uns unsigned
#define fi first
#define se second
#define IF (it->fi)
#define IS (it->se)
#define lowbit(x) ((x)&-(x))
#define END putchar('n')
#define inline jzmyyds
using namespace std;
const int MAXN=1e6+5;
const ll INF=1e18;
ll read(){
	ll x=0;bool f=1;char s=getchar();
	while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return f?x:-x;
}
int ptf[50],lpt;
void print(ll x,char c='n'){
	if(x<0)putchar('-'),x=-x;
	ptf[lpt=1]=x%10;
	while(x>9)x/=10,ptf[++lpt]=x%10;
	while(lpt)putchar(ptf[lpt--]^48);
	if(c>0)putchar(c);
}
int n,m,id[MAXN];
char a[MAXN],b[MAXN],s[MAXN];
struct PAM{
	int ch[26],len,fa,df,tf;
}td[MAXN];
int tot=1,las=0;
int initpam(){
	return td[1].len=-1,td[0].fa=td[1].fa=1,114514;
}int cbddl=initpam();
int getf(int x,int n){
	while(s[n]!=s[n-td[x].len-1])x=td[x].fa;
	return x;
}
void extend(int n){
	int p=getf(las,n),c=s[n]-'a',np=td[p].ch[c];
	if(!np){
		np=++tot,td[np].len=td[p].len+2;
		td[np].fa=td[getf(td[p].fa,n)].ch[c];
		td[p].ch[c]=np,td[np].df=td[np].len-td[td[np].fa].len;
		if(td[np].df==td[td[np].fa].df)td[np].tf=td[td[np].fa].tf;
		else td[np].tf=td[np].fa;
	}las=np;
}
int dp[MAXN],f[MAXN],pr[MAXN];
int main()
{
	*new(int)=scanf("%s%s",a+1,b+1),m=strlen(a+1);
	for(int i=1;i<=m;i++)s[++n]=a[i],id[n]=i,s[++n]=b[i],id[n]=i;
	for(int i=0;i<=tot;i++)f[i]=n+1;
	dp[n+1]=1e9;
	for(int i=1;i<=n;i++){
		extend(i),dp[i]=1e9;
		if(i>1&&s[i]==s[i-1])dp[i]=dp[i-2],pr[i]=i-2;
		for(int j=las;td[j].len>0;j=td[j].tf){
			f[j]=i-td[td[j].tf].len-td[j].df;
			if(td[j].fa^td[j].tf)f[j]=dp[f[td[j].fa]]n)return print(-1),0;
	print(dp[n]);
	for(int i=n;i>0;i=pr[i])
		if(id[pr[i]+1]^id[i])print(id[pr[i]+1],' '),print(id[i]);
	return 0;
}

若把子串向它的子串连边，那么问题就是求这个DAG的最小链覆盖，即最长反链长度。

结论1：存在一条最长反链，链上的子串长度相等。
这个不难想，考虑调整法即可。

结论2：存在一条反链长度为 k k k，等价于长度为 n − k + 1 n-k+1 n−k+1 的 k k k 个子串互不相同。
必要性很好证明。充分性的话，考虑使用结论1，链上的子串长度相等，那么长度一定 ≤ n − k + 1 ≤n-k+1 ≤n−k+1。反证法，若存在两个长度 n − k + 1 n-k+1 n−k+1 的子串相等的话，那么任何长度 ≤ n − k + 1 ≤n-k+1 ≤n−k+1 的等长子串互不相同的最多 k − 1 k-1 k−1 个，矛盾。

由此推出，若存在两个长度为 k k k 的子串相等的话，那么答案一定 < n − k + 1

我们可以先建出后缀树，然后枚举节点，此时只有子串出现的相邻位置是有用的。用树上启发式合并的话，有用的位置对的数量不超过 n log ⁡ n nlog n nlogn，所以我们把它搞下来和离线询问一起做个扫描线，用线段树维护即可。

#include//JZM yyds!!
#define ll long long//God JZM!!
#define lll __int128//JZM RollInDark!!
#define uns unsigned
#define fi first
#define se second
#define IF (it->fi)
#define IS (it->se)
#define lowbit(x) ((x)&-(x))
#define END putchar('n')
#define inline jzmyyds
using namespace std;
const int MAXN=2e5+5;
const ll INF=1e18;
ll read(){
	ll x=0;bool f=1;char s=getchar();
	while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return f?x:-x;
}
int ptf[50],lpt;
void print(ll x,char c='n'){
	if(x<0)putchar('-'),x=-x;
	ptf[lpt=1]=x%10;
	while(x>9)x/=10,ptf[++lpt]=x%10;
	while(lpt)putchar(ptf[lpt--]^48);
	if(c>0)putchar(c);
}

struct SAM{
	int ch[26],len,fa;
}sam[MAXN];
int las=1,tot=1;
int samadd(int c){
	int p=las,np=las=++tot;sam[np].len=sam[p].len+1;
	for(;p&&!sam[p].ch[c];p=sam[p].fa)sam[p].ch[c]=np;
	if(!p)sam[np].fa=1;
	else{int q=sam[p].ch[c],nq;
		if(sam[q].len==sam[p].len+1)sam[np].fa=q;
		else{
			nq=++tot,sam[nq]=sam[q],sam[nq].len=sam[p].len+1;
			sam[q].fa=sam[np].fa=nq;
			for(;p&&sam[p].ch[c]==q;p=sam[p].fa)sam[p].ch[c]=nq;
		}
	}return np;
}
int n,m,ans[MAXN];
vectorG[MAXN];
setst[MAXN];
char s[MAXN];
int MAX(int x,int y){return x>y?x:y;}
#define max MAX
#define pii pair
struct{//no-core zkw
	int f[MAXN<<1],p;
	void init(int n){for(p=1;p
		for(l=p+l-1,r=p+r+1;l^1^r;l>>=1,r>>=1){
			if(~l&1)f[l^1]=max(f[l^1],d);
			if(r&1)f[r^1]=max(f[r^1],d);
		}
	}
	int sch(int x){
		int res=0;
		for(x=p+x;x;x>>=1)res=max(res,f[x]);
		return res;
	}
}A,B;
vectorad[MAXN],sk[MAXN];
void ins(int x,int y){
	auto&s=st[x];auto it=s.insert(y).fi;
	if(it!=s.begin())it--,ad[y].emplace_back(pii(*it,sam[x].len)),it++;
	it++;
	if(it!=s.end())ad[*it].emplace_back(pii(y,sam[x].len));
}
void dfs(int x){
	for(int v:G[x]){
		dfs(v);
		if(st[x].size()
	n=read(),m=read(),*new(int)=scanf("%s",s+1);
	for(int i=1;i<=n;i++)ins(samadd(s[i]-'a'),i);
	for(int i=2;i<=tot;i++)G[sam[i].fa].push_back(i);
	dfs(1);
	for(int i=1,l;i<=m;i++)l=read(),sk[read()].emplace_back(pii(l,i));
	A.init(n),B.init(n);
	for(int i=1;i<=n;i++){
		for(auto&x:ad[i])
			A.add(1,x.fi-x.se,x.se),B.add(x.fi-x.se+1,x.fi,x.fi);
		for(auto&x:sk[i])
			ans[x.se]=i-x.fi+1-max(A.sch(x.fi),B.sch(x.fi)-x.fi+1);
	}
	for(int i=1;i<=m;i++)print(ans[i]);
	return 0;
}