QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#694889 | #9522. A Simple String Problem | Grand_Elf | AC ✓ | 560ms | 101844kb | C++17 | 3.6kb | 2024-10-31 18:53:27 | 2024-10-31 18:53:32 |
Judging History
你现在查看的是测评时间为 2024-10-31 18:53:32 的历史记录
- [2024-11-10 22:36:11]
- hack成功,自动添加数据
- (/hack/1163)
- [2024-11-06 21:48:00]
- hack成功,自动添加数据
- (/hack/1142)
- [2024-10-31 18:53:27]
- 提交
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, ans, lg[N];
string s, t;
struct SA {
int m, p, a[N], rk[N], sa[N], cnt[N], id[N], nrk[N], ht[N], f[N][20];
void work(string s) {
m = s.size();
for (int i = 1; i <= m; i++) {
a[i] = s[i];
}
for (int i = 1; i <= 127; i++) {
cnt[i] = 0;
}
for (int i = 1; i <= m; i++) {
cnt[a[i]]++;
}
for (int i = 1; i <= 127; i++) {
cnt[i] += cnt[i - 1];
}
for (int i = 1; i <= m; i++) {
sa[cnt[a[i]]--] = i;
}
p = 0;
for (int i = 1; i <= m; i++) {
rk[sa[i]] = a[sa[i]] == a[sa[i - 1]] ? p : ++p;
}
for (int w = 1; ; w <<= 1) {
for (int i = 1; i <= p; i++) {
cnt[i] = 0;
}
for (int i = 1; i <= m; i++) {
cnt[rk[i]]++;
}
for (int i = 1; i <= p; i++) {
cnt[i] += cnt[i - 1];
}
p = 0;
for (int i = 0; i < w; i++) {
id[++p] = m - i;
}
for (int i = 1; i <= m; i++) {
if (sa[i] > w) {
id[++p] = sa[i] - w;
}
}
for (int i = p; i >= 1; i--) {
sa[cnt[rk[id[i]]]--] = id[i];
}
p = 0;
for (int i = 1; i <= m; i++) {
nrk[sa[i]] = rk[sa[i]] == rk[sa[i - 1]] && rk[sa[i] + w] == rk[sa[i - 1] + w] ? p : ++p;
}
for (int i = 1; i <= m; i++) {
rk[i] = nrk[i];
}
if (p == m) {
break;
}
}
for (int i = 1, k = 0; i <= m; i++) {
if (k) {
k--;
}
while (a[i + k] == a[sa[rk[i] - 1] + k]) {
k++;
}
ht[rk[i]] = k;
}
for (int i = 1; i <= m; i++) {
f[i][0] = ht[i];
}
for (int j = 1; 1 << j <= m; j++) {
for (int i = 1; i + (1 << j) - 1 <= m; i++) {
f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
}
}
int query(int i, int j) {
int k = lg[j - i + 1];
return min(f[i][k], f[j - (1 << k) + 1][k]);
}
int lcp(int i, int j) {
int x = rk[i], y = rk[j];
if (x > y) {
swap(x, y);
}
return query(x + 1, y);
}
} S, T;
int main() {
// freopen("d.in", "r", stdin);
// freopen("d.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
for (int i = 2; i <= N - 5; i++) {
lg[i] = lg[i / 2] + 1;
}
cin >> n >> s >> t;
n++;
s = s + t.back();
t = s.front() + t;
S.work('A' + s + 'B' + t + 'C');
reverse(s.begin(), s.end());
reverse(t.begin(), t.end());
T.work('A' + s + 'B' + t + 'C');
reverse(s.begin(), s.end());
reverse(t.begin(), t.end());
for (int len = n / 2; len >= 1; len--) {
for (int i = len * 2; i <= n; i += len) {
int j = i - len;
if (T.lcp(n - j + 1, n - i + 1) + S.lcp(j + 1, i + 1) >= len || T.lcp(n + 1 + n - j + 1, n + 1 + n - i + 1) +
S.lcp(n + 1 + j + 1, n + 1 + i + 1) >= len || T.lcp(n - j + 1, n + 1 + n - i + 1) +
S.lcp(j + 1, n + 1 + i + 1) >= len) {
ans = max(ans, len);
break;
} else {
int s = T.lcp(n - j + 1, n + 1 + n - i + 1);
int p = S.lcp(j + 1, n + 1 + i + 1);
if (j - s >= 1 && T.lcp(n - (j - s) + 1, n - (i - s) + 1) >= len - s - p) {
ans = max(ans, len);
break;
}
if (i + 1 + p <= n && S.lcp(n + 1 + j + 1 + p, n + 1 + i + 1 + p) >= len - s - p) {
ans = max(ans, len);
break;
}
s = T.lcp(n + 1 + n - j + 1, n + 1 + n - i + 1);
p = S.lcp(n + 1 + j + 1, n + 1 + i + 1);
if (j - s >= 1 && T.lcp(n - (j - s) + 1, n + 1 + n - (i - s) + 1) >= len - s - p) {
ans = max(ans, len);
break;
}
s = T.lcp(n - j + 1, n - i + 1);
p = S.lcp(j + 1, i + 1);
if (i + 1 + p <= n && S.lcp(j + p + 1, n + 1 + i + p + 1) >= len - s - p) {
ans = max(ans, len);
break;
}
}
}
}
cout << ans * 2 << '\n';
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 37268kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 0ms
memory: 36724kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 3ms
memory: 36992kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 34408kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 2ms
memory: 35528kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 2ms
memory: 35652kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 532ms
memory: 101840kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 513ms
memory: 101728kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 560ms
memory: 99580kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 474ms
memory: 101652kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 420ms
memory: 99732kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 483ms
memory: 99644kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 348ms
memory: 101844kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 0ms
memory: 36744kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 3ms
memory: 35816kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 0ms
memory: 36472kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 2ms
memory: 36740kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 0ms
memory: 37192kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 0ms
memory: 36680kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 0ms
memory: 35584kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 0ms
memory: 36756kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed