QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#252837#7618. Pattern SearchSaya_Alter#WA 1ms7896kbC++141.0kb2023-11-16 13:03:062023-11-16 13:03:08

Judging History

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

  • [2023-11-16 13:03:08]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7896kb
  • [2023-11-16 13:03:06]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 2e6 + 10;

char s[N], t[N];

int n, m, nex[N], cnt[30], ct[30], ans;

void solve() {
    scanf("%s", s + 1); n = strlen(s + 1);
    scanf("%s", t + 1); m = strlen(t + 1);
    for (int i = 0; i < 26; i++) cnt[i] = ct[i] = 0;
    for (int i = 1; i <= n; i++) cnt[s[i] - 'a']++;
    for (int i = 1; i <= m; i++) {
        cnt[t[i] - 'a']--;
        if (cnt[t[i] - 'a'] < 0) {
            puts("0");
            return ;
        }
    }
    ans = 1;
    nex[1] = 0;
    for (int i = 2, j = 0; i <= m; i++) {
        while (j > 0 && t[i] != t[j + 1]) j = nex[j];
        if (t[i] == t[j + 1]) j++;
        nex[i] = j;
    }
    for (int i = nex[m] + 1; i <= m; i++) ct[t[i] - 'a']++;
    int res = 1 << 30;
    for (int i = 0; i < 26; i++) if (ct[i]) res = min(res, cnt[i] / ct[i]);
    ans += res;
    printf("%d\n", ans);
}

int main() {
    int T = 1;
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}

/*
2
bajkaaall aal
abca cba

*/

詳細信息

Test #1:

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

input:

2
bajkaaall aal
abca cba

output:

2
1

result:

ok 2 number(s): "2 1"

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 7896kb

input:

16
a a
a b
b a
aa a
ab aa
ab b
ab c
aaz az
abcde edcba
aaaaaaaaaaaabbb aaaaaaaaabb
aaaaaazz az
aaaaaaaaaz zzzzz
gggggggggggggggggggge ggggeeee
hyphyphyphyphyphyphyphyphyphyphyphyp eeeeeeeeee
hyphyphyphyphyphyphyphyphyphyphyphype eeteeteeteet
aaaabbbbbbcccccccc aaabbbbbcccccc

output:

1
0
0
2
0
1
0
1
1
1
2
0
0
0
0
1

result:

wrong answer 10th numbers differ - expected: '2', found: '1'