单调队列做法求条

#include<bits/stdc++.h>
#define rep(x,a,b) for(int x=a;x<=b;x++)
#define per(x,a,b) for(int x=a;x>=b;x--)
using namespace std;
const int N=1e5+5;
string s;
int t,n,m,k,ans;
int sa[N],rk[N],height[N];
int y[N],c[N],nowrk[N],d[N];
deque<int>q;
void add(int l,int r,int k){
	d[l]+=k,d[r+1]-=k;
}
void get_sa(){
	m=26;
	rep(i,1,n) c[(rk[i]=s[i]-'a'+1)]++;
	rep(i,1,m) c[i]+=c[i-1];
	per(i,n,1) sa[c[rk[i]]--]=i;
	for(int k=1;k<=n;k<<=1){
		int num=0;
		rep(i,n-k+1,n) y[++num]=i;
		rep(i,1,n){
			if(sa[i]>k) y[++num]=sa[i]-k;
		}
		rep(i,1,m) c[i]=0;
		rep(i,1,n) c[rk[y[i]]]++;
		rep(i,1,m) c[i]+=c[i-1];
		per(i,n,1) sa[c[rk[y[i]]]--]=y[i];
		nowrk[sa[1]]=num=1;
		rep(i,2,n){
			if(rk[sa[i]]==rk[sa[i-1]]&&rk[sa[i]+k]==rk[sa[i-1]+k]) nowrk[sa[i]]=num;
			else nowrk[sa[i]]=++num;
		}
		memcpy(rk,nowrk,(n+1)*sizeof(int));
		if(num>=n) break;
		m=num;
	}
}
void get_height(){
	//heigt[rk[i]]>=height[rk[i-1]]-1
	for(int i=1,k=0;i<=n;i++){
		if(rk[i]==1) continue;
		if(k) k--;
		int j=sa[rk[i]-1]; //不忘本来定义
		while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k]) k++;
		height[rk[i]]=k;
	}
}
void solve(){
	cin>>s>>k;
	n=s.size(),s=' '+s;
	get_sa(),get_height();
	for(int i=1,maxn=0,minn=0,j;i<=n;i++){ //枚举sa
		j=sa[i];
		if(k==1){
			maxn=max(height[i],height[i+1]);
			if(maxn>=n-j+1) continue;
			add(maxn+1,n-j+1,1);
		}
		else{
			if(i==1) continue;
			while(!q.empty()&&i-q.front()>=k-1) q.pop_front();
			while(!q.empty()&&height[i]<height[q.back()]) q.pop_back();
			q.push_back(i);
			if(i>=k){
				minn=height[q.front()];
				maxn=max(height[i-k+1],height[i+1]);
//				cout<<minn<<' '<<maxn<<'\n';
				if(minn>maxn){
//					cout<<"H"<<i<<' '<<j<<'\n';
					add(maxn+1,minn,1);
				}
			}
		}
	}
	rep(i,1,n) d[i]+=d[i-1];
//	rep(i,1,n) cout<<d[i]<<' ';
//	cout<<'\n';
	rep(i,1,n){
		if(d[i]>=d[ans]&&d[i]>0) ans=i;
	}
	cout<<(ans==0?-1:ans)<<'\n';
//	cout<<"---------\n";
	ans=0;
	while(!q.empty()) q.pop_front();
	memset(sa,0,(n+1)*sizeof(int));
	memset(rk,0,(n+1)*sizeof(int));
	memset(height,0,(n+1)*sizeof(int));
	memset(c,0,(n+1)*sizeof(int));
	memset(d,0,(n+2)*sizeof(int));
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>t;
	while(t--) solve();
	return 0;
}