列表

详情

NC237556. String Games

描述

Bob has written a string S consisting of lowercase English letters, and he is going to play a game with his 3-year-old sister Alice with the string. From now on, we denote as the length of S, S_i as the i-th character of S, and as the substring obtained by concatenating all the characters between the l-th and r-th character of S (that is, ). Note that in this problem all strings are 1-indexed.

The game will last for q rounds. In each round, both of the players need to choose a non-empty substring of S. The player with lexicographically larger string wins the game. If two player chooses the same string, it is considered a draw. Here, for two strings A and B, we say A is lexicographically larger than B if B is a prefix of A and , or there exists some non-negative integer such that and for each there holds .

Bob has already know the substring Alice will choose for each round. It is easy for him to win the game, but Alice will be really sad if Bob wins too much. Therefore, Bob wants to choose the lexicographically smallest substring of S that can help him win the game. For each round, help Bob figure out which string he should choose, or determine it is impossible to win.

输入描述

The first line of input contains a string , denoting the string that Bob writes. It is guaranteed that S only contains lowercase English letters.

The second line contains a single integer , denoting the number of rounds.

The i-th of the next q lines contains two integers , describing the i-th round in which Alice chooses  as her substring.

输出描述

Print a line for each round, indicating the string that Bob should choose. As the output may be too large if we require you to print the whole string, we only ask you to print the length and the ending character of the string. For example, if Bob's optimal string is , just print a line of . If Bob is impossible to win just print a single line of .

示例1

输入: 

aaaabb
10
2 4
2 5
3 4
3 5
5 5
1 6
3 6
4 6
5 6
6 6

输出: 

4 a
5 b
3 a
4 b
2 b
4 b
2 b
1 b
0
2 b

说明:

In the sample above, the answer strings are respectively \texttt{aaaa,aaabb,aaa,aaab,bb,aaab,ab,b,0,bb}. Note that for the 9-th query the string Alice chooses, \texttt{bb}, is the lexicographically largest substring of S, resulting in Bob having no chance to win.

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 437ms, 内存消耗: 91572K, 提交时间: 2022-10-13 16:20:36 

#include<bits/stdc++.h>
#define rep(i,s,t) for(int i=s;i<=t;++i)
using namespace std;
const int N=4e5+11;
char s[N];
int tot,n;
int to[N],nxt[N],las[N];
inline void add(int x,int y){
	nxt[++tot]=las[x];
	las[x]=tot;
	to[tot]=y;
}
namespace SAM{
	int cnt=1,las=1,o=0;
	int pos[N],ch[N][27],fa[N],l[N],id[N],ri[N],go[N];
	int Fa[N][19];
	int extend(int c){
		int np=++cnt,p=las;las=cnt;
		ri[np]=l[np]=l[p]+1;
		for(;p&&!ch[p][c];p=fa[p])
			ch[p][c]=np;
		if(!p)fa[np]=1;
		else{
			int q=ch[p][c];
			if(l[q]==l[p]+1)
				fa[np]=q;
			else{
				int nq=++cnt;
				memcpy(ch[nq],ch[q],sizeof ch[p]);
				l[nq]=l[p]+1;
				fa[nq]=fa[q],fa[q]=fa[np]=nq,ri[nq]=ri[q];
				for(;p&&ch[p][c]==q;p=fa[p])
					ch[p][c]=nq;
			}
		}
		return np;
	}
	bool cmp(int x,int y){
		return s[n+1-ri[x]+l[fa[x]]]<s[n+1-ri[y]+l[fa[y]]];
	}
	void dfs(int x,int ls){
		int a[27]={},top=0;
		for(int e=::las[x];e;e=nxt[e])
			a[++top]=to[e];
		sort(a+1,a+top+1,cmp);
		for(int i=top;i;--i){
			dfs(a[i],ls);
			ls=a[i];
		}
		go[x]=ls;
	}
	void main(){
		scanf("%s",s+1);
		int u;
		n=strlen(s+1);
		for(int i=n;i;--i){
			u=extend(s[i]-'a');
			id[u]=i,pos[i]=u;
		}
		rep(i,2,cnt){
			add(fa[i],i);
			Fa[i][0]=fa[i];
		}
		//rep(i,2,cnt)printf("%d %d\n",i,fa[i]);
		dfs(1,0);
		rep(j,1,18)
			rep(i,1,cnt)
				Fa[i][j]=Fa[Fa[i][j-1]][j-1];
		int q;
		scanf("%d",&q);
		while(q--){
			int L,R;
			scanf("%d%d",&L,&R);
			int p=pos[L];
			//printf("p=%d\n",p);
			for(int i=18;~i;--i)
				if(l[Fa[p][i]]>=R-L+1)
					p=Fa[p][i];
			if(R-L+2<=l[p]){
				printf("%d %c\n",R-L+2,s[n-ri[p]+1+(R-L+1)]);
				continue;
			}
			if(go[p]==0){
				puts("0");
			}
			else{
				printf("%d %c\n",l[fa[go[p]]]+1,s[n-ri[go[p]]+1+(l[fa[go[p]]])]);
			}
		}
	}
}
int main(){
	SAM::main();
	return 0;
}

C++ 解法, 执行用时: 285ms, 内存消耗: 30972K, 提交时间: 2022-05-28 15:52:40 

#include <bits/stdc++.h>
using namespace std;
const int MAXN =2e5+10;
#define LL long long

int sa[MAXN],r1[MAXN],r2[MAXN],tax[MAXN],hei[MAXN][30];
int *rk=r1,*tp=r2;

char s[MAXN];

void rsort(int n,int m) {
	memset(tax,0,(m+1)*sizeof(tax[0]));
	for(int i=1;i<=n;i++) tax[rk[i]]++;
	for(int i=1;i<=m;i++) tax[i]+=tax[i-1];
	for(int i=n;i;i--) sa[tax[rk[tp[i]]]--]=tp[i];
}

void get_sa(char *s) {
	int n=strlen(s+1), m=0;
	for(int i=1;i<=n;i++)
		m=max(m,rk[i]=s[i]),tp[i]=i;
	rsort(n,m);
	for(int k=1,p=0;p<n;k<<=1,m=p) {
		p=0;
		for(int i=n-k+1;i<=n;i++) {
			tp[++p]=i;
		}
		for(int i=1;i<=n;i++)
			if(sa[i]>k)
				tp[++p]=sa[i]-k;
		
		rsort(n,m);
		
		swap(tp,rk);
		
		rk[sa[1]]=p=1;
		for(int i=2;i<=n;i++) {
			rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]] && tp[sa[i]+k]==tp[sa[i-1]+k])?p:++p;
		}
	}
	
	for(int i=1,k=0;i<=n;i++) {
		if(k) k--;
		while(rk[i]>1 && s[i+k]==s[sa[rk[i]-1]+k]) k++;
		hei[rk[i]][0]=k;
	}
	
	for(int i=2;i<=n;i++) {
		for(int j=1;i-(1<<j)>=0;j++) {
			hei[i][j]=min(hei[i][j-1],hei[i-(1<<(j-1))][j-1]);
		}
	}
}

//char s[MAXN];

void solve() {
	scanf("%s", s+1);
	int n=strlen(s+1);
	get_sa(s);
//	for(int i=1;i<=n;i++)
//		cout<<hei[i][0]<<' ';
//	puts("");
	int q;
	scanf("%d", &q);
	while(q--) {
		int l,r;
		scanf("%d %d", &l, &r);
		int a=r-l+1;
		int rank=rk[l];
		int cur=rk[l];
//		cout<<cur<<endl;
		for(int d = 29; d >= 0; d--)
			if(hei[cur][d] >= a){
				cur = cur - (1 << d);
			}
//		cout<<"cur:"<<cur<<endl;
		if(n-sa[cur]+1==a) {
			if(cur==n) puts("0");
			else {
				cur++;
				a=min(a,hei[cur][0]);
				printf("%d %c\n", a+1, s[sa[cur]+a]);
			}
		} else {
//			cout<<"a:"<<a<<endl;
			printf("%d %c\n", a+1, s[sa[cur]+a]);
		}
	}
}

int main() {
	int T=1;
	while(T--) {
		solve();
	}
	return 0;
}

上一题

© 2025 nowcoder.com