QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#761044 | #9522. A Simple String Problem | Clarus | AC ✓ | 509ms | 74608kb | C++20 | 4.8kb | 2024-11-18 20:42:24 | 2024-11-18 20:42:30 |
Judging History
answer
#include <bits/stdc++.h>
using LL = long long;
struct SA
{
int n;
std::vector<int> sa, rk, lc;
SA(std::string s) : n(s.size()), sa(n), rk(n), lc(n - 1, -1)
{
std::iota(sa.begin(), sa.end(), 0);
std::sort(sa.begin(), sa.end(), [&](int a, int b)
{
return s[a] < s[b];
});
rk[sa[0]] = 0;
for (int i = 1; i < n; i++)
{
rk[sa[i]] = rk[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);
}
std::vector<int> tmp, cnt(n);
tmp.reserve(n);
for (int k = 1; rk[sa[n - 1]] < n - 1; k *= 2)
{
tmp.clear();
for (int i = 0; i < k; i++)
{
tmp.push_back(n - k + i);
}
for (auto i : sa)
{
if (i >= k)
{
tmp.push_back(i - k);
}
}
std::fill(cnt.begin(), cnt.end(), 0);
for (int i = 0; i < n; i++)
{
cnt[rk[i]]++;
}
for (int i = 1; i < n; i++)
{
cnt[i] += cnt[i - 1];
}
for (int i = n - 1; i >= 0; i--)
{
sa[-- cnt[rk[tmp[i]]]] = tmp[i];
}
std::swap(rk, tmp);
rk[sa[0]] = 0;
for (int i = 1; i < n; i++)
{
rk[sa[i]] = rk[sa[i - 1]] +
(tmp[sa[i - 1]] < tmp[sa[i]] || sa[i - 1] + k == n ||
tmp[sa[i - 1] + k] < tmp[sa[i] + k]);
}
}
for (int i = 0, j = 0; i < n; i++)
{
if (rk[i] == 0)
{
j = 0;
}
else
{
for (j -= j > 0; i + j < n && sa[rk[i] - 1] + j < n && s[i + j] == s[sa[rk[i] - 1] + j]; j++);
lc[rk[i] - 1] = j;
}
}
}
};
void chmax(int &a, int b)
{
a = a > b ? a : b;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::string s, t;
std::cin >> s >> t;
s += " " + t;
int m = s.size();
SA s1(s), s2(std::string(s.rbegin(), s.rend()));
int logm = std::__lg(m);
std::vector st1(logm + 1, std::vector<int>(m));
std::vector st2(logm + 1, std::vector<int>(m));
st1[0] = s1.lc, st2[0] = s2.lc;
for (int j = 0; j < logm; j++)
{
for (int i = 0; i + (2 << j) <= m; i++)
{
st1[j + 1][i] = std::min(st1[j][i], st1[j][i + (1 << j)]);
st2[j + 1][i] = std::min(st2[j][i], st2[j][i + (1 << j)]);
}
}
auto &sa1 = s1.sa, &sa2 = s2.sa;
auto &rk1 = s1.rk, &rk2 = s2.rk;
auto lcp = [&](int l, int r) -> int // [l, r)
{
l = rk1[l];
r = rk1[r];
assert(l != r);
if (l > r)
{
std::swap(l, r);
}
int k = std::__lg(r - l);
return std::min(st1[k][l], st1[k][r - (1 << k)]);
};
auto lcs = [&](int l, int r) -> int // [l, r)
{
l = rk2[m - 1 - l];
r = rk2[m - 1 - r];
assert(l != r);
if (l > r)
{
std::swap(l, r);
}
int k = std::__lg(r - l);
return std::min(st2[k][l], st2[k][r - (1 << k)]);
};
for (int d = n; d > 0; d--)
{
for (int i = 0; i + d < m; i += d)
{
int j = i + d;
if (j <= n || i >= n)
{
int l = i, r = j;
if (j <= n) { r += n; }
if (i >= n) { l -= n; }
int x = lcp(l, r) + lcs(l, r) - 1;
int y = 0;
if (r + lcp(l, r) < m)
{
chmax(y, lcp(l + lcp(l, r) + n, r + lcp(l, r)));
}
if (l - lcs(l, r) >= 0)
{
chmax(y, lcs(l - lcs(l, r), r - lcs(l, r) - n));
}
if (x + y >= d)
{
std::cout << 2 * d << '\n';
return 0;
}
}
int x = lcp(i, j) + lcs(i, j) - 1;
int y = 0;
if (i > n && i - lcs(i, j) - n >= 0)
{
chmax(y, lcs(i - lcs(i, j) - n, j - lcs(i, j)));
}
else if (j < n && j + lcp(i, j) + n < m)
{
chmax(y, lcp(i + lcp(i, j), j + lcp(i, j) + n));
}
if (x + y >= d)
{
std::cout << 2 * d << '\n';
return 0;
}
}
}
std::cout << 0 << '\n';
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3524kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3504kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 261ms
memory: 74372kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 253ms
memory: 74456kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 250ms
memory: 74420kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 509ms
memory: 74376kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 204ms
memory: 74608kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 216ms
memory: 74372kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 446ms
memory: 74324kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed