UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#203842#2133. buzztkswls100104ms29008kbC++111.8kb2024-03-24 10:16:302024-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,我给组数据试试?

Details

小提示:点击横条可展开更详细的信息

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