QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#689013 | #9522. A Simple String Problem | FDUdululu | AC ✓ | 949ms | 85912kb | C++20 | 5.3kb | 2024-10-30 14:53:01 | 2024-11-10 22:37:47 |
Judging History
你现在查看的是最新测评结果
- [2024-11-10 22:36:11]
- hack成功,自动添加数据
- (/hack/1163)
- [2024-11-06 21:48:00]
- hack成功,自动添加数据
- (/hack/1142)
- [2024-10-30 14:53:01]
- 提交
answer
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 4e5 + 5; // |S|
const int M = 30; // max ASCII(s_i)
const int K = 20; // log N
int n;
string a, b;
char s[N], t[N];
struct SuffixArray {
int n, m = M;
int sa[N], rk[N], ht[N], tax[N], tmp[N];
int st[N][K], lg[N];
void init(int N) {
n = N;
for (int i = 0; i <= n + 1; i++) {
sa[i] = rk[i] = ht[i] = 0;
tax[i] = tmp[i] = 0;
}
for (int i = 0; i < K; i++)
for (int j = 0; j <= n + 1; j++)
st[i][j] = n;
m = M;
SA();
get_ht();
build();
}
void Qsort() {
for (int i = 0; i <= m; i++)
tax[i] = 0;
for (int i = 1; i <= n; i++)
tax[rk[i]]++;
for (int i = 1; i <= m; i++)
tax[i] += tax[i - 1];
for (int i = n; i >= 1; i--)
sa[tax[rk[tmp[i]]]--] = tmp[i];
}
int cmp(int x, int y, int w) {
return (tmp[x] == tmp[y] && tmp[x + w] == tmp[y + w]);
}
void SA() {
for (int i = 1; i <= n; i++) {
rk[i] = s[i] - 'a' + 1;
tmp[i] = i;
}
Qsort();
for (int w = 1; w <= n; w <<= 1) {
int p = 0;
for (int i = n - w + 1; i <= n; i++)
tmp[++p] = i;
for (int i = 1; i <= n; i++)
if (sa[i] > w)
tmp[++p] = sa[i] - w;
Qsort();
swap(tmp, rk);
rk[sa[1]] = p = 1;
for (int i = 2; i <= n; i++)
rk[sa[i]] = cmp(sa[i - 1], sa[i], w) ? p : ++p;
if (p == n)
break;
m = p;
}
}
void get_ht() { // ht[i] = lcp(sa[i], sa[i - 1])
for (int i = 1, k = 0; i <= n; i++) {
if (k)
--k;
// 多测记得防越界
// 或者 s[] 开两倍空间,清空后一半
// while ((i + k <= n && sa[rk[i] - 1] + k <= n) && s[i + k] == s[sa[rk[i] - 1] + k])
// k++;
while (s[i + k] == s[sa[rk[i] - 1] + k])
k++;
ht[rk[i]] = k;
}
}
void build() {
for (int i = 2; i <= n; i++) // index starts with 2
lg[i] = lg[i >> 1] + 1;
for (int i = 1; i <= n; i++)
st[i][0] = ht[i];
for (int i = 1; i < K; i++)
for (int j = 1; j + (1 << i) - 1 <= n; j++)
st[j][i] = min(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
}
int query(int L, int R) { // lcp(s[i,n],s[j,n])
if (L < 1 || L > n || R < 1 || R > n)
return 0;
int l, r;
l = min(rk[L], rk[R]) + 1;
r = max(rk[L], rk[R]);
int t = lg[r - l + 1];
return min(st[l][t], st[r - (1 << t) + 1][t]);
}
} f, g;
void solve() {
cin >> n;
cin >> a >> b;
a = " " + a, b = " " + b;
s[n + 1] = '{';
for (int i = 1; i <= n; i++)
s[i] = a[i], s[n + 1 + i] = b[i];
for (int i = 1; i <= 2 * n + 1; i++)
t[i] = s[i];
f.init(2 * n + 1);
reverse(s + 1, s + 2 * n + 1 + 1);
g.init(2 * n + 1);
int ans = 0;
for (int len = 1; len <= n; len++) {
for (int i = 1; i <= n; i += len) {
int pre, suf, nxtsuf, nxtpre;
// a
pre = g.query(2 * n + 1 - i + 1, 2 * n + 1 - (i + len) + 1);
suf = f.query(i, i + len);
if (pre + suf > len)
ans = max(ans, 2 * len);
// b
pre = g.query(2 * n + 1 - (n + 1 + i) + 1, 2 * n + 1 - (n + 1 + i + len) + 1);
suf = f.query(n + 1 + i, n + 1 + i + len);
if (pre + suf > len)
ans = max(ans, 2 * len);
// a + b
// aa
pre = g.query(2 * n + 1 - (i) + 1, 2 * n + 1 - (i + len) + 1);
suf = f.query(i, i + len);
nxtsuf = f.query((i + suf), n + 1 + (i + len + suf - 1));
if (pre + suf + nxtsuf > len)
ans = max(ans, 2 * len);
// ab
pre = g.query(2 * n + 1 - (i) + 1, 2 * n + 1 - (n + 1 + i + len - 1) + 1);
suf = f.query(i, n + 1 + (i + len - 1));
nxtpre = g.query(2 * n + 1 - (i - pre) + 1, 2 * n + 1 - (i + len - 1 - pre + 1) + 1);
nxtsuf = f.query(n + 1 + (i + suf - 1), n + 1 + (i + len - 1 + suf));
if (pre + suf + max(nxtsuf, nxtpre) > len)
ans = max(ans, 2 * len);
// bb
pre = g.query(2 * n + 1 - (n + 1 + i + len - 1) + 1, 2 * n + 1 - (n + 1 + i + 2 * len - 1) + 1);
suf = f.query(n + 1 + i + len - 1, n + 1 + (i + 2 * len - 1));
nxtpre = g.query(2 * n + 1 - (i + len - 1 - pre + 1) + 1, 2 * n + 1 - (n + 1 + i + 2 * len - 1 - pre) + 1);
if (pre + suf + nxtpre > len)
ans = max(ans, 2 * len);
}
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
while (T--) {
solve();
}
return 0;
}
/*
5
abcab
acabc
6
babbaa
babaaa
2
ne
fu
*/
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 22376kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 0ms
memory: 22044kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 3ms
memory: 21972kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 4ms
memory: 22456kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 5ms
memory: 22076kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 4ms
memory: 22232kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 907ms
memory: 85680kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 886ms
memory: 85912kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 896ms
memory: 85872kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 687ms
memory: 85612kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 737ms
memory: 85668kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 949ms
memory: 85768kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 738ms
memory: 85748kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 2ms
memory: 22076kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 0ms
memory: 21968kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 0ms
memory: 21916kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 4ms
memory: 22044kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 5ms
memory: 22020kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 3ms
memory: 20112kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 3ms
memory: 24052kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 5ms
memory: 22268kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed