ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#203842 | #2133. buzz | tkswls | 100 | 104ms | 29008kb | C++11 | 1.8kb | 2024-03-24 10:16:30 | 2024-03-24 12:07:11 |
answer
#include<bits/stdc++.h>
using namespace std;
int son[2005][30], cnt, fail[2005], a[2005], f[2005][2005], from[2005][2005], ffrom[2005][2005];
string s, t;
int n, m;
void add() {
int w = 0;
for (int i = 0; i < n; i++) {
if (son[w][t[i] - 'a'] != 0) {
w = son[w][t[i] - 'a'];
} else {
son[w][t[i] - 'a'] = ++cnt;
w = cnt;
}
}
}
void build() {
queue<int> q;
for (int i = 0; i < 26; i++) {
if (son[0][i] != 0) {
q.push(son[0][i]);
}
}
while (q.size()) {
int p = q.front();
q.pop();
for (int i = 0; i < 26; i++) {
if (son[p][i] != 0) {
fail[son[p][i]] = son[fail[p]][i];
q.push(son[p][i]);
} else {
son[p][i] = son[fail[p]][i];
}
}
}
}
inline void print(int p, int q) {
if (!p) return;
print(p - 1, from[p][q]);
cout << char('a' + ffrom[p][q]);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> s >> t;
m = s.size(), n = t.size();
for (int i = 1; i <= m; i++) {
if (s[i - 1] == '?') a[i] = -1;
else a[i] = s[i - 1] - 'a';
}
add();
build();
memset(f, -0x3f, sizeof(f));
f[0][0] = 0;
for (int i = 1; i <= m; i++) {
for (int j = 0; j <= cnt; j++) {
if (a[i] == -1) {
for (int k = 0; k < 26; k++) {
if (f[i - 1][j] > f[i][son[j][k]] ) {
f[i][son[j][k]] = f[i - 1][j];
from[i][son[j][k]] = j;
ffrom[i][son[j][k]] = k;
}
}
} else {
if (f[i - 1][j] > f[i][son[j][a[i]]]) {
f[i][son[j][a[i]]] = f[i - 1][j];
from[i][son[j][a[i]]] = j;
ffrom[i][son[j][a[i]]] = a[i];
}
}
}
if (f[i][cnt] >= 0)f[i][cnt]++;
}
int ans = -1, maxb = -1;
for (int j = 0; j <= cnt; j++) {
if (f[m][j] > ans) {
ans = f[m][j];
maxb = j;
}
}
cout << ans << "\n";
print(m, maxb);
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 0ms
memory: 25116kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
result:
ok good job
Test #2:
score: 0
Accepted
time: 0ms
memory: 25052kb
input:
vlsfijcaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
490 vlsfijcaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
result:
ok good job
Test #3:
score: 0
Accepted
time: 4ms
memory: 25048kb
input:
ababababababababababababababaabababababababababaabababababababababababababababababababababababababab...
output:
1 ababababababababababababababaabababababababababaababababababababababababababababababababababababab...
result:
ok good job
Test #4:
score: 0
Accepted
time: 0ms
memory: 25000kb
input:
kqfoatydjehqkwsujxerxpeannihrcevphskryrjbgseewacdcryrzxqqisxkxbdwqrhmuknxefppfxbtvxbqfoatydjehqkwsuj...
output:
5 kqfoatydjehqkwsujxerxpeannihrcevphskryrjbgseewacdcryrzxqqisxkxbdwqrhmuknxefppfxbtvxbqfoatydjehqkws...
result:
ok good job
Test #5:
score: 0
Accepted
time: 0ms
memory: 24996kb
input:
pzaabbaabbcacabccacaaaccbbcbabaabcaccbabbaaaaabbcacabccacaaaccbbcbabaabcaccbabbaaaccabbbcabbaaabbaba...
output:
5 pzaabbaabbcacabccacaaaccbbcbabaabcaccbabbaaaaabbcacabccacaaaccbbcbabaabcaccbabbaaaccabbbcabbaaabba...
result:
ok good job
Test #6:
score: 0
Accepted
time: 0ms
memory: 24996kb
input:
dubaabbcaaabcabaabbcaaabcacbccaacabbccbabcbbcbabbcaabbaaabcabbaabbcbbbccabbcbabcabaccaaabbccabcaaccc...
output:
4 dubaabbcaaabcabaabbcaaabcacbccaacabbccbabcbbcbabbcaabbaaabcabbaabbcbbbccabbcbabcabaccaaabbccabcaac...
result:
ok good job
Test #7:
score: 0
Accepted
time: 4ms
memory: 24996kb
input:
vsvobhthrlknganweporrieihdvqwhjiloujphxktsgojyusvobsvobhthrlknganweporrieihdvqwhjiloujphxsvobhtsvobh...
output:
3 vsvobhthrlknganweporrieihdvqwhjiloujphxktsgojyusvobsvobhthrlknganweporrieihdvqwhjiloujphxsvobhtsvo...
result:
ok good job
Test #8:
score: 0
Accepted
time: 3ms
memory: 25000kb
input:
bacbacbbbbabababaccabcacacbabacbacbbbbabababaccabcacacbccccabcaacccacccbbbaababcccccacccbaaabcaaacaa...
output:
6 bacbacbbbbabababaccabcacacbabacbacbbbbabababaccabcacacbccccabcaacccacccbbbaababcccccacccbaaabcaaac...
result:
ok good job
Test #9:
score: 0
Accepted
time: 7ms
memory: 25000kb
input:
eevlqaabcabcbabbabbccabcbbbacaabbacaacbbabbccacacbcaabbbcbbccaabcabcbabbabbccabcbbbacaabbacaacbbabbc...
output:
4 eevlqaabcabcbabbabbccabcbbbacaabbacaacbbabbccacacbcaabbbcbbccaabcabcbabbabbccabcbbbacaabbacaacbbab...
result:
ok good job
Test #10:
score: 0
Accepted
time: 4ms
memory: 16984kb
input:
l nyrwecxqyldyabnmccgfqzimpvmycmekumsdcunqqxctmplhqytkfmvoomyynhamioueyqeyrcsxcjobvioefuexipfauwlibuxh
output:
0 l
result:
ok good job
Subtask #2:
score: 20
Accepted
Test #11:
score: 20
Accepted
time: 3ms
memory: 17380kb
input:
aaa?a?aaaa??aa?aaaa?aaaaaaaaaaaaaaaa??aaa?aaa?aaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
output:
1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
result:
ok good job
Test #12:
score: 0
Accepted
time: 0ms
memory: 17372kb
input:
???aa??a?????aaa??aaa?a?aaaaa?aa?a????a?a????a??aa aaaaaaaaaaaaaaaaaaaaaaaaa
output:
26 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
result:
ok good job
Test #13:
score: 0
Accepted
time: 4ms
memory: 17364kb
input:
ababa??babaaba?ababababa?abababa????aba?ab?bab?bab abababababababababababab
output:
1 ababacbbabaababababababababababababbabacabbbabbbab
result:
ok good job
Test #14:
score: 0
Accepted
time: 0ms
memory: 17360kb
input:
ssz??os??xozs?osz?xo??szs?o?oszs??szs????zsx?xo?xo szsxo
output:
7 sszsxoszsxozsaoszsxoaaszsxoaoszsxoszsxoaszsxoxoaxo
result:
ok good job
Test #15:
score: 0
Accepted
time: 0ms
memory: 17364kb
input:
bb?bcb?a?cbabcbabcba??bc?cbc??bbb?ab?bcb??ab?abcbo babcb
output:
7 bbabcbbabcbabcbabcbabcbcacbcaabbbbabcbcbcaabbabcbo
result:
ok good job
Test #16:
score: 0
Accepted
time: 4ms
memory: 17364kb
input:
a???cbc?a?b?acbc?a???ba????cb?bb???cbc??????bcbb?? acbcb
output:
6 aacbcbcbabbbacbcbacbcbacbcbcbbbbacbcbcacbcbbbcbbbb
result:
ok good job
Test #17:
score: 0
Accepted
time: 0ms
memory: 17360kb
input:
ookmo?kokm?aoo?okmqaaook?qaq?ak?kokokokmqaokmq?qaa okmqa
output:
5 ookmoakokmqaooaokmqaaookmqaqaakakokokokmqaokmqaqaa
result:
ok good job
Test #18:
score: 0
Accepted
time: 3ms
memory: 17360kb
input:
c??????aacbcb?b?c?aa???b????c?bc??b??c??c??????caa cbbca
output:
6 cbbcaaaaacbcbcbbcaaaacbbcaaacbbcaabaacbbcacbbcacaa
result:
ok good job
Test #19:
score: 0
Accepted
time: 0ms
memory: 17360kb
input:
cbcbcb?c?cbccb?bcbcb?c?bc?cc?cc?cbc?c?bcbcbcbc?cbc cbcbc
output:
14 cbcbcbccbcbccbcbcbcbcccbcbccaccbcbcbccbcbcbcbcbcbc
result:
ok good job
Test #20:
score: 0
Accepted
time: 0ms
memory: 16968kb
input:
? oktyf
output:
0 a
result:
ok good job
Subtask #3:
score: 60
Accepted
Test #21:
score: 60
Accepted
time: 12ms
memory: 29008kb
input:
aaaaaaaaa??aaa??a?aaaaaa?aa?aaa?aa?a?a?aa?aaaaaaaaaaa?aaaaaaa?a?aa??aa???aaaaaaa?aaaaaaaaaa?aaa?aaaa...
output:
1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
result:
ok good job
Test #22:
score: 0
Accepted
time: 19ms
memory: 27880kb
input:
?r???ckss?w?uwgwzwkaaaaa?aa??aaa????????aa?a?aaaa?aa???a????a?a?a??a?a???aaa?a?aaaaaaaaaa?aaa?a????a...
output:
482 brbbbckssbwbuwgwzwkaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
result:
ok good job
Test #23:
score: 0
Accepted
time: 4ms
memory: 27376kb
input:
ababab??aababa?a?aba???aba??baba??bababab?baba??baba?ab?bababababa?aba?abab?ba?ababaaba?ababab??abab...
output:
177 abababbbaababacacabacbbabacbbabacbbabababbbabacbbabacabbbababababacabacababbbacababaabababababab...
result:
ok good job
Test #24:
score: 0
Accepted
time: 13ms
memory: 25224kb
input:
tnv?h?f????????????y?i???jos?????kl??io?i?zgxwixo??ys?a??oq?r?wg???g??wrjv?oj?m??hdsqn?sv?a????v??m?...
output:
5 tnvahafaaaaaaaaaaaayaiaiqjosphzgtklyfioliczgxwixocsysyaaioqrrdwgunygubwrjvgojvmldhdsqnrsvzawawmvkb...
result:
ok good job
Test #25:
score: 0
Accepted
time: 0ms
memory: 25196kb
input:
a?abaaccabaa?cabcbaaa?aaccabaaccabcb??aba?a?baaccbc?caccaaaaaa?aac?aba?cca?cb?cabababbaaccbcc???b?ac...
output:
4 ababaaccabaabcabcbaaacaaccabaaccabcbbbabababbaaccbcbcaccaaaaaacaacbababccabcbbcabababbaaccbccaaaba...
result:
ok good job
Test #26:
score: 0
Accepted
time: 4ms
memory: 25260kb
input:
v?a??f??f??a?aa??ab?c??a?a?a????c?bbbcccac?c??b??bcab?c????b?c??cc???a??ca?b??b????cc??b???c?aaa??bc...
output:
4 vbabbfbbfbbabaabbabbcbbabababbbbcbbbbcccacbcbbbbbbcabbcbbbbbbcbbccbbbabbcabbbbbbbbbccbbbbbbcbaaabb...
result:
ok good job
Test #27:
score: 0
Accepted
time: 9ms
memory: 25160kb
input:
bgkigt??bohrv??qsuqzshprdcgcqubel?yychnkfg?jtwruqzhkgdchopl?v??fesuqzshprdcgcqubelfyychnkfgbjtwruqzh...
output:
4 bgkigtaabohrvaaqsuqzshprdcgcqubelayychnkfgajtwruqzhkgdchoplavaafesuqzshprdcgcqubelfyychnkfgbjtwruq...
result:
ok good job
Test #28:
score: 0
Accepted
time: 4ms
memory: 25212kb
input:
hlxw??c?bac???cc?bcaaab??c??ab?c?bab???aabc??abb?a?abba????c?cba????cc????ca?bc??bc??a??cc???b?ca??b...
output:
4 hlxwbbcbbacbbbccbbcaaabbbcbbabbcbbabbbbaabcbbabbbababbabbbbcbcbabbbbccbbbbcabbcbbbcbbabbccbbbbbcab...
result:
ok good job
Test #29:
score: 0
Accepted
time: 3ms
memory: 25216kb
input:
??tegoljbjmxsxjyxb?cc?cbbccaabcbac?bbc?cccabac?a?c??abbc?abbcccbcccacbbccaabcccacbcccbcccacbbcc?abcb...
output:
4 aategoljbjmxsxjyxbaccacbbccaabcbacabbcacccabacaaacaaabbcaabbcccbcccacbbccaabcccacbcccbcccacbbccaab...
result:
ok good job
Test #30:
score: 0
Accepted
time: 0ms
memory: 16980kb
input:
? avmchmvshklgvywbukpisrticiapcznpphhzmkseufyxbnmkjzuhwgncnjzfvriamtiwmyjxecikmjfoxzwvvqlzpneizwcwuccv
output:
0 b
result:
ok good job
Extra Test:
score: 0
Extra Test Passed