QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#683948 | #9522. A Simple String Problem | ucup-team3215 | AC ✓ | 832ms | 79992kb | C++23 | 3.9kb | 2024-10-28 04:07:22 | 2024-10-28 04:07:23 |
Judging History
你现在查看的是测评时间为 2024-10-28 04:07:23 的历史记录
- [2024-11-10 22:36:11]
- hack成功,自动添加数据
- (/hack/1163)
- [2024-11-06 21:48:00]
- hack成功,自动添加数据
- (/hack/1142)
- [2024-10-28 15:17:17]
- hack成功,自动添加数据
- (/hack/1080)
- [2024-10-28 14:28:57]
- hack成功,自动添加数据
- (/hack/1079)
- [2024-10-28 04:07:22]
- 提交
answer
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define sz(c) (int)c.size()
#define all(c) c.begin(),c.end()
#define rep(i, l, r) for(int i =l;i < r;++i)
struct SuffixArray {
vi sa, lcp;
SuffixArray(string &s, int lim = 256) { // or basic_string<int>
int n = sz(s) + 1, k = 0, a, b;
vi x(all(s)), y(n), ws(max(n, lim));
x.push_back(0), sa = lcp = y, iota(all(sa), 0);
for (int j = 0, p = 0; p < n; j = max(1, j * 2), lim = p) {
p = j, iota(all(y), n - j);
rep(i, 0, n) if (sa[i] >= j) y[p++] = sa[i] - j;
fill(all(ws), 0);
rep(i, 0, n) ws[x[i]]++;
rep(i, 1, lim) ws[i] += ws[i - 1];
for (int i = n; i--;) sa[--ws[x[y[i]]]] = y[i];
swap(x, y), p = 1, x[sa[0]] = 0;
rep(i, 1, n) a = sa[i - 1], b = sa[i], x[b] =
(y[a] == y[b] && y[a + j] == y[b + j]) ? p - 1 : p++;
}
for (int i = 0, j; i < n - 1; lcp[x[i++]] = k)
for (k &&k--, j = sa[x[i] - 1];
s[i + k] == s[j + k];
k++);
}
};
constexpr int LOG = 20;
int main() {
cin.tie(0)->sync_with_stdio(false);
int n;
cin >> n;
string s, t;
cin >> s >> t;
int res = 0;
auto solve = [&] {
string q = s;
q += 'z' + 1;
q += t;
q += 'z' + 2;
q += string(s.rbegin(), s.rend());
q += 'z' + 3;
q += string(t.rbegin(), t.rend());
auto SA = SuffixArray(q);
vector<vector<int>> sp(LOG);
int N = SA.sa.size();
sp[0] = SA.lcp;
for (int i = 1; i < LOG; ++i) {
sp[i].resize(N);
for (int j = 0; j + (1 << i) - 1 < sp[i].size(); ++j) {
sp[i][j] = min(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);
}
}
vector<int> pos(N);
for (int i = 0; i < N; ++i) {
pos[SA.sa[i]] = i;
}
auto ask = [&](int l, int r) {
if (l >= r)return 0;
int len = r - l;
int lg = __lg(len);
return min(sp[lg][l], sp[lg][r - (1 << lg)]);
};
auto lcp = [&](int x, int y) {
x = pos[x], y = pos[y];
if (x > y)swap(x, y);
if (x < 0 || y > N)return 0;
return ask(x + 1, y + 1);
};
auto rev = [&](int i) {
return n - i - 1;
};
for (int l = 1; l <= n; ++l) {
for (int i = 0; i + l - 1 < n; i += l) {
// stupid
{
int lq = i, rq = i + l - 1;
rq += lcp(i, i + l);
lq -= lcp(rev(i + l - 1) + 2 * (n + 1), rev(i - 1) + 2 * (n + 1));
if (rq - lq + 1 >= 2 * l) {
res = max(res, l);
continue;
}
rq += lcp(i + (rq + 1) % l, rq + 1 + (n + 1) - 1);
if (rq - lq + 1 >= 2 * l) {
res = max(res, l);
}
}
{
int pf = lcp(i, i + l + (n + 1) - 1);
int sf = lcp(rev(i - 1) + 2 * (n + 1), rev(i + l - 1 - 1) + 3 * (n + 1));
if (pf + sf >= l) {
res = max(res, l);
continue;
}
int need = l - pf - sf;
if (lcp(rev(i + l - 1 - sf) + 2 * (n + 1), rev(i - 1 - sf) + 2 * (n + 1)) >= need)res = max(res, l);
if (lcp(i + pf + (n + 1) - 1, i + l + pf + (n + 1) - 1) >= need)res = max(res, l);
}
}
}
};
solve();
swap(s, t);
reverse(s.begin(), s.end());
reverse(t.begin(), t.end());
solve();
cout << res * 2;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3536kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 832ms
memory: 79320kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 802ms
memory: 79468kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 816ms
memory: 78728kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 669ms
memory: 79992kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 611ms
memory: 79096kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 748ms
memory: 78592kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 515ms
memory: 79844kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed