QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#245935 | #4669. Genetic Modifications | Rain | RE | 1ms | 7912kb | C++14 | 2.0kb | 2023-11-10 14:41:23 | 2023-11-10 14:41:24 |
Judging History
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...