QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#731162 | #9522. A Simple String Problem | Moyou | WA | 348ms | 96908kb | C++14 | 4.0kb | 2024-11-10 00:15:22 | 2024-11-10 00:15:27 |
Judging History
This is a historical verdict posted at 2024-11-10 00:15:27.
- [2024-11-10 22:36:11]
- hack成功,自动添加数据
- (/hack/1163)
- [2024-11-10 00:15:22]
- Submitted
answer
// Problem: A Simple String Problem
// Contest: Virtual Judge - Gym
// Author: Moyou
// Copyright (c) 2024 Moyou All rights reserved.
// Date: 2024-11-09 22:28:04
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
// #define int long long
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;
const int N = 4e5 + 10;
int n, m;
string s, t, S, RS;
struct SuffixArray {
int n, sa[N * 2], rk[N * 2], sa2[N * 2], x[N], buc[N], ht[N], sig, lg[N], st[20][N];
void SA(string s) {
n = s.size() - 1;
for(int i = 1; i <= n; i ++) rk[i] = s[i], sig = max(sig, rk[i]), buc[rk[i]] ++;
for(int i = 1; i <= sig; i ++) buc[i] += buc[i - 1];
for(int i = 1; i <= n; i ++) sa[buc[rk[i]] --] = i;
for(int j = 1, idx = 0; idx < n; j *= 2, sig = idx) {
idx = 0; for(int i = n - j + 1; i <= n; i ++) sa2[++ idx] = i;
for(int i = 1; i <= n; i ++) if(sa[i] > j) sa2[++ idx] = sa[i] - j;
for(int i = 1; i <= sig; i ++) buc[i] = 0;
for(int i = 1; i <= n; i ++) x[i] = rk[sa2[i]], buc[x[i]] ++;
for(int i = 1; i <= sig; i ++) buc[i] += buc[i - 1];
for(int i = n; i; i --) sa[buc[x[i]] --] = sa2[i];
idx = 1, swap(sa2, rk), rk[sa[1]] = 1;
for(int i = 2; i <= n; i ++) {
if(sa2[sa[i]] == sa2[sa[i - 1]] && sa2[sa[i] + j] == sa2[sa[i - 1] + j]) rk[sa[i]] = idx;
else rk[sa[i]] = ++ idx;
}
// cout << idx << '\n';
}
for(int i = 1, l = 0; i <= n; i ++) {
if(l) l --;
while(i + l <= n && sa[rk[i] - 1] + l <= n && s[i + l] == s[sa[rk[i] - 1] + l]) l ++;
ht[rk[i]] = l;
}
// for(int i = 1; i <= n; i ++) cout << rk[i] << ' '; cout << endl;
// for(int i = 1; i <= n; i ++) cout << ht[rk[i]] << ' '; cout << endl;
}
void ST() {
for(int i = 1; i <= n; i ++) st[0][i] = ht[i];
for(int i = 2; i <= n; i ++) lg[i] = lg[i >> 1] + 1;
for(int i = 1; i <= lg[n]; i ++)
for(int j = 1; j + (1 << i) - 1 <= n; j ++)
st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
}
int LCP(int l, int r, bool op = 0) {
if(l == r) return 0;
if(op) l = n - l + 1, r = n - r + 1;
if(l < 1 || l > n || r < 1 || r > n) return 0;
if((l = rk[l]) > (r = rk[r])) swap(l, r);
int k = lg[r - l];
return min(st[k][l + 1], st[k][r - (1 << k) + 1]);
}
} po, ro;
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> s >> t;
s += '$', t = "#" + t;
S = s + t, RS = S;
int stt = s.size();
reverse(RS.begin(), RS.end());
S = " " + S, RS = " " + RS;
po.SA(S), po.ST(), ro.SA(RS), ro.ST();
// cout << S << "\n" << RS << '\n';
// cout << po.LCP(3, 12) << '\n';
for(int len = (n + 1) / 2; len; len --) {
for(int p = 1; p <= n + 1; p += len) {
int x = po.LCP(p + stt, p + len + stt), y = ro.LCP(p - 1 + stt, stt + p + len - 1, 1);
int pos1 = p - 1 - y, pos2 = p + len - 1 - y;
int z = ro.LCP(pos1, stt + pos2, 1);
if(x + y + z >= len) return cout << len * 2, 0;
x = ro.LCP(p - 1, p + len - 1, 1), y = po.LCP(p, p + len);
pos1 = p + y, pos2 = p + len + y;
z = po.LCP(pos1, pos2 + stt);
// if(len == 3) cout << x << ' ' << y << ' ' << pos1 << ' ' << pos2 + stt << ' ' << z << '\n';
if(x + y + z >= len) return cout << len * 2, 0;
if(ro.LCP(p - 1, p + len - 1 + stt, 1) + po.LCP(p, p + len) >= len) return cout << len * 2, 0;
}
}
cout << 0 << '\n';
return 0;
}
/*
aabba$#baaba
aabba$
#baaba
a b c a b $ # a c a b c
3 7 12 9 1 5 11 4 10 2 6 8
5 9 11 3 7 2 1 6 12 4 8 10
5 9 11 3 7 2 1 6 12 4 8 10
abcab$
#acabc
*/
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 38500kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 4ms
memory: 40708kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 0ms
memory: 34592kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 38620kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 2ms
memory: 38692kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 3ms
memory: 38392kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 217ms
memory: 96448kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 199ms
memory: 94524kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 238ms
memory: 96908kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 348ms
memory: 96580kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 172ms
memory: 94856kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 183ms
memory: 95508kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 309ms
memory: 95424kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 0ms
memory: 46592kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 3ms
memory: 46660kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 0ms
memory: 46592kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 0ms
memory: 46852kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 3ms
memory: 38460kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 2ms
memory: 38404kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 0ms
memory: 50688kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 0ms
memory: 46888kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed