QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#725860 | #9522. A Simple String Problem | warner1129 | AC ✓ | 343ms | 76084kb | C++20 | 6.2kb | 2024-11-08 20:19:00 | 2024-11-10 22:38:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
template<class F, class S>
ostream &operator<<(ostream &s, const pair<F, S> &v) {
s << "(" << v.first << ", " << v.second << ")";
return s;
}
template<ranges::range T> requires (!is_convertible_v<T, string_view>)
istream &operator>>(istream &s, T &&v) {
for (auto &&x : v) s >> x;
return s;
}
template<ranges::range T> requires (!is_convertible_v<T, string_view>)
ostream &operator<<(ostream &s, T &&v) {
for (auto &&x : v) s << x << ' ';
return s;
}
#ifdef LOCAL
template<class... T> void dbg(T... x) {
char e{};
((cerr << e << x, e = ' '), ...);
}
#define debug(x...) dbg(#x, '=', x, '\n')
#else
#define debug(...) ((void)0)
#endif
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define ff first
#define ss second
template<class T> inline constexpr T inf = numeric_limits<T>::max() / 2;
bool chmin(auto &a, auto b) { return (b < a and (a = b, true)); }
bool chmax(auto &a, auto b) { return (a < b and (a = b, true)); }
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
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-- and !t[y]) sa[x[s[y] - 1]++] = y;
for (auto x = c; int y : sa | views::reverse)
if (y-- and 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(
s.begin() + j, s.begin() + j + len,
s.begin() + i, s.begin() + 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;
}
// sa[i]: sa[i]-th suffix is the
// i-th lexicographically smallest suffix.
// lcp[i]: LCP of suffix sa[i] and suffix sa[i + 1].
struct Suffix {
int n;
vector<int> sa, rk, lcp;
Suffix(const auto &s) : n(s.size()),
lcp(n - 1), rk(n) {
vector<int> t(n + 1); // t[n] = 0
copy(all(s), t.begin()); // s shouldn't contain 0
sa = sais(t); sa.erase(sa.begin());
for (int i = 0; i < n; i++) rk[sa[i]] = i;
for (int i = 0, h = 0; i < n; i++) {
if (!rk[i]) { h = 0; continue; }
for (int j = sa[rk[i] - 1];
i + h < n and j + h < n
and s[i + h] == s[j + h];) ++h;
lcp[rk[i] - 1] = h ? h-- : 0;
}
}
};
template<class T>
struct SparseTable {
function<T(T, T)> F;
vector<vector<T>> st;
int n;
SparseTable(const vector<T> &V, const auto &f) {
F = f;
n = V.size();
int lgN = __lg(n);
st.assign(lgN + 1, vector<T>(n));
st[0] = V;
for (int i = 0; i < lgN; i++)
for (int j = 0; j + (2 << i) <= n; j++)
st[i + 1][j] = F(st[i][j], st[i][j + (1 << i)]);
}
T qry(int l, int r) { // [l, r)
int h = __lg(r - l);
return F(st[h][l], st[h][r - (1 << h)]);
}
};
void solve() {
int n;
cin >> n;
string S;
cin >> S;
S += 'z' + 1;
{
string t;
cin >> t;
S += t;
}
Suffix suf(S), rev(string(rall(S)));
auto Min = [&](int a, int b) {
return min(a, b);
};
SparseTable<int> sufmin(suf.lcp, Min), revmin(rev.lcp, Min);
auto lcp = [&](int a, int b) {
if (min(a, b) < 0 or max(a, b) > 2 * n) {
return 0;
}
a = suf.rk[a];
b = suf.rk[b];
if (a > b) {
swap(a, b);
}
return sufmin.qry(a, b);
};
auto lcs = [&](int a, int b) {
if (min(a, b) < 0 or max(a, b) > 2 * n) {
return 0;
}
a = 2 * n - a;
b = 2 * n - b;
a = rev.rk[a];
b = rev.rk[b];
if (a > b) {
swap(a, b);
}
return revmin.qry(a, b);
};
int ans = 0;
for (int d = (n + 1) / 2; d >= 1; d--) {
for (int i = 0; i + d <= n + 1; i += d) {
if (lcp(i, i + d) + lcs(i - 1, i + d - 1) >= d) {
ans = 2 * d;
break;
}
if (lcp(n + i, n + i + d) + lcs(n + i - 1, n + i + d - 1) >= d) {
ans = 2 * d;
break;
}
if (lcp(i, n + i + d) + lcs(i - 1, n + i + d - 1) >= d) {
ans = 2 * d;
break;
}
int j = i - lcs(i - 1 + n, i + d - 1 + n);
int k = i + d + lcp(i + n, i + d + n);
int p = j - lcs(j - 1, j + d - 1 + n);
if (k - p >= 2 * d) {
ans = 2 * d;
break;
}
j = i - lcs(i - 1, i + d - 1);
k = i + d + lcp(i, i + d);
p = k + lcp(k - d, k + n);
if (p - j >= 2 * d) {
ans = 2 * d;
break;
}
}
if (ans != 0) {
break;
}
}
cout << ans << '\n';
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3572kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3568kb
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: 99ms
memory: 76084kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 96ms
memory: 75956kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 109ms
memory: 75968kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 259ms
memory: 75140kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 81ms
memory: 75472kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 92ms
memory: 75004kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 343ms
memory: 75896kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3580kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed