QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#246501 | #4669. Genetic Modifications | Eznibuil | RE | 0ms | 1652kb | C++14 | 787b | 2023-11-10 21:21:36 | 2023-11-10 21:21:37 |
Judging History
answer
#include<stdio.h>
#include<string.h>
char s[100005],t[100005];
int l[100005],r[100005];
int main()
{
scanf("%s%s",s+1,t+1),l[0]=r[0]=0;
int lt=strlen(t+1)+1;
for(int i=1;i<lt;i++)
{
if(s[l[i-1]+1]==t[i])
l[i]=l[i-1]+1;
else
for(l[i]=l[i-1]+1;s[l[i-1]+1]==s[l[i]];l[i]++);
if(s[r[i-1]+1]==t[i])
for(r[i]=r[i-1]+1;s[r[i-1]+1]==s[r[i]+1];r[i]++);
else
for(r[i]=r[i-1]+1;s[r[i-1]+1]==s[r[i]];r[i]++);
}
if(!s[l[lt-1]])
return printf("NO"),0;
for(int i=r[lt-1]+1;s[i];i++)
if(s[i]!=s[r[lt-1]+1])
return printf("NO"),0;
puts("YES");
for(int i=lt-1;i;i--)
{
int j=i<lt-1?l[i+1]-1:strlen(s+1);
for(;s[j-1]==s[j];j--);
if(l[i]<j-1)
l[i]=j-(t[i]==s[j-1]);
}
for(int i=1;i<lt;i++)
printf("%d ",l[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 1608kb
input:
BBAAABBAAABAAA BAAB
output:
YES 2 5 8 11
result:
ok good solution
Test #2:
score: 0
Accepted
time: 0ms
memory: 1492kb
input:
ABABABABAB ABAB
output:
NO
result:
ok no solution
Test #3:
score: 0
Accepted
time: 0ms
memory: 1652kb
input:
BBAAAAABBAAAAAABBABAABBBBBAABBBAAABABBABABBBAAABBAAAABBBBBABAABBBAABBBBBBBABBABABBAAAABBAAAABAAAABBABAAAAAAABBBBAAAAAABAABABBAAAAABBBBAABABABAAAAABBBABABBAABABBBBAABAABBBBBABBABABBAAABBAAAABBBABBABAAAABBBAABAAABBBAAAAAAAAAAAAABABBAABBBBABABAABBBBABAABBAAABABBBBAAAAAAAABBAAAABBABABABBBAAABAABBABBAAAA...
output:
NO
result:
ok no solution
Test #4:
score: -100
Runtime Error
input:
BABABAABABBABAAAAABAABBAAAAABABABBABABBBBBBBAAAAAAABAAAAABAABBABBABABBBABBBAAAABBBABABBAAAABBBAABBBBBBBAAAABAAAABBBBABBAABAABBBAABBBBABAABABBBBAABABBABBAABAABBBBBAAABBAABABBBBAABABBABAABAAAABBABABAABBBABBBBABABABABAAABBABABABABBABAABBBBABAABBABBBBABABBABBBBBAABBBBBAAABAABAAAABBBBBABBABABABBBBABBBABA...