QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#703880 | #9522. A Simple String Problem | 1e11 | AC ✓ | 305ms | 79916kb | C++20 | 4.6kb | 2024-11-02 18:46:11 | 2024-11-10 22:38:11 |
Judging History
你现在查看的是最新测评结果
- [2024-11-10 22:36:11]
- hack成功,自动添加数据
- (/hack/1163)
- [2024-11-06 21:48:00]
- hack成功,自动添加数据
- (/hack/1142)
- [2024-11-02 18:46:11]
- 提交
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define all(v) begin(v), end(v)
auto sais(const auto &s) {
const int n = (int)s.size(), z = ranges::max(s) + 1;
if (n == 1) return vector{0};
vector<int> c(z); for (int x : s) ++c[x];
partial_sum(all(c), begin(c));
vector<int> sa(n); auto I = views::iota(0, n);
vector<bool> t(n); t[n - 1] = true;
for (int i = n - 2; i >= 0; --i)
t[i] = (s[i] == s[i + 1] ? t[i + 1] : s[i] < s[i + 1]);
auto is_lms = views::filter([&t](int x) {
return x && t[x] && !t[x - 1]; });
auto induce = [&] {
for (auto x = c; int y : sa)
if (y--) if (!t[y]) sa[x[s[y] - 1]++] = y;
for (auto x = c; int y : sa | views::reverse)
if (y--) if (t[y]) sa[--x[s[y]]] = y;
};
vector<int> lms, q(n); lms.reserve(n);
for (auto x = c; int i : I | is_lms) {
q[i] = int(lms.size());
lms.push_back(sa[--x[s[i]]] = i);
}
induce(); vector<int> ns(lms.size());
for (int j = -1, nz = 0; int i : sa | is_lms) {
if (j >= 0) {
int len = min({n - i, n - j, lms[q[i] + 1] - i});
ns[q[i]] = nz += lexicographical_compare(begin(s) + j, begin(s) + j + len, begin(s) + i, begin(s) + i + len);
}
j = i;
}
ranges::fill(sa, 0); auto nsa = sais(ns);
for (auto x = c; int y : nsa | views::reverse)
y = lms[y], sa[--x[s[y]]] = y;
return induce(), sa;
}
struct Suffix {
int n;
vector<int> sa, hi, rev;
Suffix(const auto &s) : n(int(s.size())), hi(n), rev(n) {
vector<int> _s(n + 1);
copy(all(s), begin(_s));
sa = sais(_s); sa.erase(sa.begin());
for (int i = 0; i < n; ++i) rev[sa[i]] = i;
for (int i = 0, h = 0; i < n; ++i) {
if (!rev[i]) { h = 0; continue; }
for (int j = sa[rev[i] - 1]; i + h < n && j + h < n && s[i + h] == s[j + h];) ++h;
hi[rev[i]] = h ? h-- : 0;
}
}
};
template <int LG = 20> struct SparseTableSA : Suffix {
array<vector<int>, LG> mn;
SparseTableSA(const auto &s) : Suffix(s), mn{hi} {
for (int l = 0; l + 1 < LG; l++) { mn[l + 1].resize(n);
for (int i = 0, len = 1 << l; i + len < n; i++)
mn[l + 1][i] = min(mn[l][i], mn[l][i + len]);
}
}
int lcp(int a, int b) {
if (a == b) return n - a;
a = rev[a] + 1, b = rev[b] + 1;
if (a > b) swap(a, b);
const int lg = __lg(b - a);
return min(mn[lg][a], mn[lg][b - (1 << lg)]);
}
pair<int, int> get_range(int x, int len) {
int a = rev[x] + 1, b = rev[x] + 1;
for (int l = LG - 1; l >= 0; l--) {
const int s = 1 << l;
if (a + s <= n && mn[l][a] >= len) a += s;
if (b - s >= 0 && mn[l][b - s] >= len) b -= s;
}
return {b - 1, a};
}
};
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
string S, T;
cin >> S >> T;
S = S + '$';
T = '%' + T;
++n;
auto rS = S, rT = T;
reverse(all(rS));
reverse(all(rT));
auto F = '!' + S + '#' + T + '@';
SparseTableSA sa('!' + S + '#' + T + '@');
SparseTableSA rsa('!' + rS + '#' + rT + '@');
auto OS = 1;
auto OT = n + 2;
for (int len = n; len >= 1; len--) {
auto ok = [len] {
cout << len * 2 << '\n';
exit(0);
};
for (int i = 0; i + len < n; i += len) {
int a = i, b = i + len;
{
int x = sa.lcp(a + OS, b + OT);
int y = rsa.lcp(n - a + OS, n - b + OT);
x += sa.lcp(a + x + OT, b + x + OT);
if (x + y >= len)
ok();
}
{
int x = sa.lcp(a + OS, b + OT);
int y = rsa.lcp(n - a + OS, n - b + OT);
y += rsa.lcp(n - (a - y) + OS, n - (b - y) + OS);
if (x + y >= len)
ok();
}
{
int x = sa.lcp(a + OT, b + OT);
int y = rsa.lcp(n - a + OT, n - b + OT);
y += rsa.lcp(n - (a - y) + OS, n - (b - y) + OT);
if (x + y >= len)
ok();
}
{
int x = sa.lcp(a + OS, b + OS);
int y = rsa.lcp(n - a + OS, n - b + OS);
x += sa.lcp(a + x + OS, b + x + OT);
if (x + y >= len)
ok();
}
}
}
cout << 0 << '\n';
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3780kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 83ms
memory: 78572kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 84ms
memory: 78396kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 111ms
memory: 78676kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 219ms
memory: 77368kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 63ms
memory: 78552kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 81ms
memory: 79916kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 305ms
memory: 78360kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed