QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#246169 | #4669. Genetic Modifications | MYFJCHC | WA | 1ms | 3828kb | C++14 | 1.1kb | 2023-11-10 16:52:31 | 2023-11-10 16:52:31 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m;
char s[N], t[N];
int nxt[N], f[N], g[N];
int main()
{
scanf("%s%s", s + 1, t + 1);
n = strlen(s + 1), m = strlen(t + 1);
for(int i = 1; i <= n; i ++ ) nxt[i] = s[i] == s[i - 1] ? nxt[i - 1] : i - 1;
// for(int i = 1; i <= n; i ++ ) printf("%d ", nxt[i]);
// puts("");
g[m + 1] = n + 1;
for(int i = m, j = n; i > 0 && j > 0; i -- , j -- )
{
if(t[i] != s[j]) j = nxt[j];
else j = nxt[j] + 1;
if(j > 0) g[i] = j;
}
if(g[1] && nxt[g[1] - 1] == 0)
{
puts("YES");
for(int k = 1; k <= m; k ++ ) printf("%d ", g[k]);
return 0;
}
for(int i = 1, j = 1; i <= m && j <= n; i ++ , j ++ )
{
while(j <= m && t[i] != s[j]) j ++ ;
f[i] = j;
if(j <= m && g[i + 1] > j && nxt[g[i + 1] - 1] <= j)
{
puts("YES");
for(int k = 1; k <= i; k ++ ) printf("%d ", f[k]);
for(int k = i + 1; k <= m; k ++ ) printf("%d ", g[k]);
return 0;
}
}
// for(int i = 1; i <= m; i ++ ) printf("%d ", f[i]);
// puts("");
// for(int i = 1; i <= m; i ++ ) printf("%d ", g[i]);
// puts("");
puts("NO");
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3828kb
input:
BBAAABBAAABAAA BAAB
output:
YES 2 5 8 11
result:
ok good solution
Test #2:
score: 0
Accepted
time: 0ms
memory: 3420kb
input:
ABABABABAB ABAB
output:
NO
result:
ok no solution
Test #3:
score: 0
Accepted
time: 1ms
memory: 3776kb
input:
BBAAAAABBAAAAAABBABAABBBBBAABBBAAABABBABABBBAAABBAAAABBBBBABAABBBAABBBBBBBABBABABBAAAABBAAAABAAAABBABAAAAAAABBBBAAAAAABAABABBAAAAABBBBAABABABAAAAABBBABABBAABABBBBAABAABBBBBABBABABBAAABBAAAABBBABBABAAAABBBAABAAABBBAAAAAAAAAAAAABABBAABBBBABABAABBBBABAABBAAABABBBBAAAAAAAABBAAAABBABABABBBAAABAABBABBAAAA...
output:
NO
result:
ok no solution
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 3656kb
input:
BABABAABABBABAAAAABAABBAAAAABABABBABABBBBBBBAAAAAAABAAAAABAABBABBABABBBABBBAAAABBBABABBAAAABBBAABBBBBBBAAAABAAAABBBBABBAABAABBBAABBBBABAABABBBBAABABBABBAABAABBBBBAAABBAABABBBBAABABBABAABAAAABBABABAABBBABBBBABABABABAAABBABABABABBABAABBBBABAABBABBBBABABBABBBBBAABBBBBAAABAABAAAABBBBBABBABABABBBBABBBABA...
output:
NO
result:
wrong answer you didn't find a solution but jury did