QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#245935#4669. Genetic ModificationsRainRE 1ms7912kbC++142.0kb2023-11-10 14:41:232023-11-10 14:41:24

Judging History

你现在查看的是最新测评结果

  • [2023-11-10 14:41:24]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:7912kb
  • [2023-11-10 14:41:23]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10,M=2010;
int n,m,ne[M][M],ne1[N][30],g[N];
char a[N],b[N];
bool f[M][M],f1[N][30];
vector<int>v;
inline void solve(){
	int i=1,cnt=0;
	if(a[1]==b[1]){
		while(i<=n){
			while(i<n&&a[i]==a[i+1]) ++i;
			v.push_back(i);
			++i;++cnt;
		}
		if(cnt<m||cnt>m+1) puts("NO");
		else{
			puts("YES");
			for(int j=0;j<m;++j) printf("%d ",v[j]);
		}
	}
	else{
		while(i<n&&a[i]==a[i+1]) ++i;
		++i;++cnt;
		while(i<=n){
			v.push_back(i);
			while(i<n&&a[i]==a[i+1]) ++i;
			++i;++cnt;
		}
		if(cnt!=m+1) puts("NO");
		else{
			puts("YES");
			for(int j=0;j<m;++j) printf("%d ",v[j]);
		}
	}
}
int main(){
	scanf("%s%s",a+1,b+1);
	n=strlen(a+1),m=strlen(b+1);
//	printf("%s\n%s\n",a+1,b+1);
	bool fg=1;
	for(int i=1;i<m;++i){
		if(b[i]==b[i+1]){
			fg=0;
			break;
		}
	}
	if(fg) return solve(),0;
	if(m<=20){
		int la=0;
		memset(g,-1,sizeof g);
		g[0]=0;
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				if(a[i]==b[j]&&~g[j-1]) ne1[i][j]=g[j-1],f1[i][j]=1;
			}
			if(i>1&&a[i]!=a[i-1]){
				la=i-1;
				for(int j=0;j<m;++j) g[j]=(f1[i-1][j]?i-1:-1);
			}
			for(int j=0;j<m;++j) if(f1[i][j]) g[j]=i;
		}
		for(int i=la;i<=n;++i){
			if(f1[i][m]){
				puts("YES");
				int u=i;
				for(int j=m;j;--j){
					v.push_back(u);
					u=ne1[u][j];
				}
				for(int j=m-1;~j;--j) printf("%d ",v[j]);
				return 0;
			}
		}
		puts("NO");
	}
	else{
		f[0][0]=1;
		int la=0;
		memset(g,-1,sizeof g);
		g[0]=0;
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				if(a[i]==b[j]&&~g[j-1]) ne[i][j]=g[j-1],f[i][j]=1;
			}
			if(i>1&&a[i]!=a[i-1]){
				la=i-1;
				for(int j=0;j<m;++j) g[j]=(f[i-1][j]?i-1:-1);
			}
			for(int j=0;j<m;++j) if(f[i][j]) g[j]=i;
		}
		for(int i=la;i<=n;++i){
			if(f[i][m]){
				puts("YES");
				int u=i;
				for(int j=m;j;--j){
					v.push_back(u);
					u=ne[u][j];
				}
				for(int j=m-1;~j;--j) printf("%d ",v[j]);
				return 0;
			}
		}
		puts("NO");
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7912kb

input:

BBAAABBAAABAAA
BAAB

output:

YES
2 5 8 11 

result:

ok good solution

Test #2:

score: 0
Accepted
time: 1ms
memory: 5824kb

input:

ABABABABAB
ABAB

output:

NO

result:

ok no solution

Test #3:

score: -100
Runtime Error

input:

BBAAAAABBAAAAAABBABAABBBBBAABBBAAABABBABABBBAAABBAAAABBBBBABAABBBAABBBBBBBABBABABBAAAABBAAAABAAAABBABAAAAAAABBBBAAAAAABAABABBAAAAABBBBAABABABAAAAABBBABABBAABABBBBAABAABBBBBABBABABBAAABBAAAABBBABBABAAAABBBAABAAABBBAAAAAAAAAAAAABABBAABBBBABABAABBBBABAABBAAABABBBBAAAAAAAABBAAAABBABABABBBAAABAABBABBAAAA...

output:


result: