QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #384192 | #3698. Censor | rukong | AC ✓ | 47ms | 36952kb | C++20 | 861b | 2024-04-09 20:56:21 | 2024-04-09 20:56:22 |
Judging History
answer
#include <iostream>
#include <vector>
using namespace std;
const int N = 5000100;
int nex[N];
void getnext(string &a)
{
int i = 0, k = -1;
nex[0] = -1;
while (i < a.size())
{
if (k == -1 || a[i] == a[k])
{
i++, k++;
if (a[i] == a[k])
nex[i] = nex[k];
else
nex[i] = k;
}
else
k = nex[k];
}
}
void kmp(string &b, string &a)
{
vector<char>ans(b.size() + 1);
vector<int>num(b.size() + 1);
int j = 0, top = 0;
for (int i = 0; i < b.size(); i++)
{
ans[++top] = b[i];
while (j != -1 && b[i] != a[j])
j = nex[j];
j++;
num[top] = j;
if (j == a.size())
{
top -= a.size();
j = num[top];
}
}
for (int i = 1; i <= top; i++)
cout << ans[i];
cout << '\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
string a, b;
while (cin >> a >> b)
{
getnext(a);
kmp(b, a);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3828kb
input:
abc aaabcbc
output:
a
result:
ok "a"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
b bbb
output:
result:
ok 0 tokens
Test #3:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
abc ab
output:
ab
result:
ok "ab"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
a a
output:
result:
ok 0 tokens
Test #5:
score: 0
Accepted
time: 30ms
memory: 34308kb
input:
psbxsnuvsjxqxaxtenaeamkeiexxrxjedktjovzchfagxtuufdpkbygqomxcgtatpqbkmtfejjobotujqtsemecytkcrnjgsltmlwvskbwncdtruokaisoqembgdmbjrmdehxlqdxyqyrhncvxntsqolhgcmzqkbswtmajbfxgrowadtjernqvhndbdyjchjniakmufkojzykdcvhnfahiyugbeujvpjddroflvktkbijgqpwdowtxjcoelwzlwbarnrlkgzwenifjduqlulsqlbhyqpoyvycbltpacjzctr...
output:
oegqzaeamymfahlivlcmvkzygvfqsmswsjvramhldsijvbckvplzctcqoanhmdzkdonbzibkbtgjvcghwjrzsqnkrpbfclizatdoxoezdhyktljopqpvctzspwvgkjwrznuqxhebximatsznunienlrvggrqqxscftwveakyeulomfroocwycvtwkhugbwoaelrrelqhyrazflgworbngfknlfzpwmzruuwpswvjrulqixaayhtygfcaioegvxcostrbolmlihcwflxsyvgqjmrgioytgrpnlexmylfqslgs...
result:
ok "oegqzaeamymfahlivlcmvkzygvfqsm...gkdljsilibmvlswatdofwrwsaltvmhg"
Test #6:
score: 0
Accepted
time: 15ms
memory: 33100kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
result:
ok "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
Test #7:
score: 0
Accepted
time: 25ms
memory: 34472kb
input:
ababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbab...
output:
abbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabba...
result:
ok "abbabbababbababbabbababbababba...ababbabbababbababbabbababbabbab"
Test #8:
score: 0
Accepted
time: 24ms
memory: 32976kb
input:
gluotgkgvemqkxnhkcbagxxnneujamscmzsehglfaoyonhvlencqhgwoqaxkxzhvkdwdsoweyiypneyjzvioatvzscdeyekoktktljrtslaykowttrgxskdannclzdoikbzfubgemcpwdsljgzfdzhgvvnbpljrdtdwbzllvetzbmkkbprpwypixocbxvtlbvptvrxnshoopfkeqfcmxcnkujoourtinvxwptbqpeabfqelwojanvlxtpaiivhjlwuazwixbngtlpaffotwqzrblmxnhoubsyqifxxrzgfki...
output:
dvvloxkccarswflgydmjonurioutqmmwfjmniyghdccxhwyqlrqekecsxwjlawsufzjgopbeawcuqseccbompyozyaoouucdydbwsnzsrpaxywkpdewyznfeaoulvldrfhzzttyzslqyezxzikgpfeptmykvnkankrbetwtaqdcpsltenyvhqbivgwysmbjunabmdlhunadaimgfycczkdvjqoiiwkxsuekjkaupmwewhezdtiaimlfjbilaqkcofezxoovflddrkipiftliswkdghbhbkwncvsxbzrgiuax...
result:
ok "dvvloxkccarswflgydmjonurioutqm...oiedsimtummptasitamhsdaplxjkwei"
Test #9:
score: 0
Accepted
time: 47ms
memory: 35176kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
aaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaabaaaaaaaa...
result:
ok "aaaaaaaaaaaaaaaaaaaaaaaaaabaaa...aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
Test #10:
score: 0
Accepted
time: 20ms
memory: 36952kb
input:
babbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabb...
output:
babbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabb...
result:
ok "babbababbabbababbababbabbababb...bababbababbabbababbababbabbabab"