QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#246506 | #4669. Genetic Modifications | Eznibuil | RE | 0ms | 1664kb | C11 | 800b | 2023-11-10 21:25:37 | 2023-11-10 21:25:38 |
Judging History
answer
#include<stdio.h>
#include<string.h>
char s[200001],t[200001];
int l[200001],r[200001];
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-(t[i]==s[j-1]))
l[i]=j-(t[i]==s[j-1]);
}
for(int i=1;i<lt;i++)
printf("%d ",l[i]);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 1584kb
input:
BBAAABBAAABAAA BAAB
output:
YES 2 5 8 11
result:
ok good solution
Test #2:
score: 0
Accepted
time: 0ms
memory: 1524kb
input:
ABABABABAB ABAB
output:
NO
result:
ok no solution
Test #3:
score: 0
Accepted
time: 0ms
memory: 1664kb
input:
BBAAAAABBAAAAAABBABAABBBBBAABBBAAABABBABABBBAAABBAAAABBBBBABAABBBAABBBBBBBABBABABBAAAABBAAAABAAAABBABAAAAAAABBBBAAAAAABAABABBAAAAABBBBAABABABAAAAABBBABABBAABABBBBAABAABBBBBABBABABBAAABBAAAABBBABBABAAAABBBAABAAABBBAAAAAAAAAAAAABABBAABBBBABABAABBBBABAABBAAABABBBBAAAAAAAABBAAAABBABABABBBAAABAABBABBAAAA...
output:
NO
result:
ok no solution
Test #4:
score: -100
Runtime Error
input:
BABABAABABBABAAAAABAABBAAAAABABABBABABBBBBBBAAAAAAABAAAAABAABBABBABABBBABBBAAAABBBABABBAAAABBBAABBBBBBBAAAABAAAABBBBABBAABAABBBAABBBBABAABABBBBAABABBABBAABAABBBBBAAABBAABABBBBAABABBABAABAAAABBABABAABBBABBBBABABABABAAABBABABABABBABAABBBBABAABBABBBBABABBABBBBBAABBBBBAAABAABAAAABBBBBABBABABABBBBABBBABA...