QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#734080 | #9522. A Simple String Problem | becaido | AC ✓ | 651ms | 75288kb | C++20 | 5.7kb | 2024-11-10 23:46:24 | 2024-11-10 23:46:24 |
Judging History
answer
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
vector<int> suffix_array(string s) {
int n = s.size();
if (n == 1) return {0};
s += "\0";
vector<int> sa(n + 1), rnk(n + 1), cnt(n + 1);
array<int, 256> alp{};
for (int i = 0; i <= n; i++) alp[s[i]]++;
for (int i = 1; i < 256; i++) alp[i] += alp[i - 1];
for (int i = 0; i <= n; i++) sa[--alp[s[i]]] = i;
for (int i = 1, cur = 0; i <= n; i++) {
if (s[sa[i]] != s[sa[i - 1]]) cur++;
rnk[sa[i]] = cur;
}
for (int len = 1; len <= n; len <<= 1) {
vector<int> lp(n + 1), nrnk(n + 1);
fill(cnt.begin(), cnt.end(), 0);
for (int i = 0; i <= n; i++) {
lp[i] = sa[i] - len;
if (lp[i] < 0) lp[i] += n + 1;
cnt[rnk[i]]++;
}
for (int i = 1; i <= n; i++) cnt[i] += cnt[i - 1];
for (int i = n; i >= 0; i--) sa[--cnt[rnk[lp[i]]]] = lp[i];
nrnk[sa[0]] = 0;
for (int i = 1, cur = 0; i <= n; i++) {
int np1 = sa[i] + len, np2 = sa[i - 1] + len;
if (np1 > n + 1) np1 -= n + 1;
if (np2 > n + 1) np2 -= n + 1;
if (rnk[sa[i]] != rnk[sa[i - 1]] || rnk[np1] != rnk[np2]) cur++;
nrnk[sa[i]] = cur;
}
rnk = nrnk;
}
sa.erase(sa.begin());
return sa;
}
vector<int> lcp_array(string s, vector<int> sa = {}) {
int n = s.size(), len = 0;
if (sa.size() == 0) sa = suffix_array(s);
vector<int> rnk(n), lcp(n - 1);
for (int i = 0; i < n; i++) rnk[sa[i]] = i;
for (int i = 0; i < n; i++) {
if (rnk[i] == n - 1) {
len = 0;
continue;
}
int j = sa[rnk[i] + 1];
while (i + len < n && j + len < n && s[i + len] == s[j + len]) len++;
lcp[rnk[i]] = len;
len = max(0, len - 1);
}
return lcp;
}
const int SIZE = 4e5 + 500;
const int H = __lg(SIZE);
int n;
string a, b, s1, s2;
vector<int> sa1, sa2, rnk1, rnk2, lcp1, lcp2;
struct ST {
int mn[SIZE][H + 1];
void build(vector<int> v) {
int n = v.size();
FOR (i, 0, n - 1) mn[i][0] = v[i];
for (int j = 1, len = 2; len <= n; j++, len <<= 1) {
FOR (i, 0, n - len) {
mn[i][j] = min(mn[i][j - 1], mn[i + (len >> 1)][j - 1]);
}
}
}
int que(int l, int r) {
if (l == r) return n;
r--;
int h = __lg(r - l + 1);
return min(mn[l][h], mn[r - (1 << h) + 1][h]);
}
} st1, st2;
int lcp(int t1, int l1, int r1, int t2, int l2, int r2) {
if (l1 > r1 || l2 > r2) return 0;
int x = (t1 == 0 ? rnk1[l1] : rnk1[n + l1]);
int y = (t2 == 0 ? rnk1[l2] : rnk1[n + l2]);
if (x > y) swap(x, y);
int re = st1.que(x, y);
re = min({re, r1 - l1 + 1, r2 - l2 + 1});
return re;
}
int lcs(int t1, int l1, int r1, int t2, int l2, int r2) {
if (l1 > r1 || l2 > r2) return 0;
int x = (t1 == 0 ? rnk2[2 * n - r1 - 1] : rnk2[n - r1 - 1]);
int y = (t2 == 0 ? rnk2[2 * n - r2 - 1] : rnk2[n - r2 - 1]);
if (x > y) swap(x, y);
int re = st2.que(x, y);
re = min({re, r1 - l1 + 1, r2 - l2 + 1});
return re;
}
void solve() {
cin >> n >> a >> b;
n++, a += "$", b = "$" + b;
s1 = s2 = a + b;
reverse(s2.begin(), s2.end());
sa1 = suffix_array(s1), lcp1 = lcp_array(s1, sa1);
sa2 = suffix_array(s2), lcp2 = lcp_array(s2, sa2);
st1.build(lcp1), st2.build(lcp2);
rnk1.resize(sa1.size()), rnk2.resize(sa2.size());
FOR (i, 0, sa1.size() - 1) {
rnk1[sa1[i]] = i;
rnk2[sa2[i]] = i;
}
for (int len = (n + 1) / 2; len >= 1; len--) {
for (int l = 0, r = len - 1; r < n; l += len, r += len) {
{
int R = r + lcp(1, l, n - 1, 1, r + 1, n - 1);
int L = l - lcs(1, 0, r, 1, 0, l - 1);
int aL = L - lcs(1, L, L + len - 1, 0, 0, L - 1);
if (R - aL + 1 >= 2 * len) {
cout << 2 * len << '\n';
return;
}
}
{
int L = l - lcs(0, 0, r, 0, 0, l - 1);
int R = r + lcp(0, l, n - 1, 0, r + 1, n - 1);
int bR = R + lcp(0, R - len + 1, R, 1, R + 1, n - 1);
if (bR - L + 1 >= 2 * len) {
cout << 2 * len << '\n';
return;
}
}
{
int len1 = lcs(0, 0, l - 1, 1, l, r);
int len2 = lcp(1, r + 1, n - 1, 0, l, r);
if (len1 + len2 >= len) {
cout << 2 * len << '\n';
return;
}
int len3 = len2 + lcp(1, r + 1 + len2, n - 1, 1, l + len2, r);
if (len1 + len3 >= len) {
cout << 2 * len << '\n';
return;
}
len3 = len1 + lcs(0, 0, l - 1 - len1, 0, l, r - len1);
if (len2 + len3 >= len) {
cout << 2 * len << '\n';
return;
}
}
}
}
cout << "0\n";
}
int main() {
Waimai;
solve();
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 5628kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5624kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 1ms
memory: 5632kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 1ms
memory: 5660kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 1ms
memory: 5840kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 1ms
memory: 5680kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 291ms
memory: 75228kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 276ms
memory: 74044kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 278ms
memory: 75240kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 562ms
memory: 75288kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 200ms
memory: 75064kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 195ms
memory: 75128kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 651ms
memory: 75224kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 1ms
memory: 5924kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 1ms
memory: 5692kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 1ms
memory: 5636kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 1ms
memory: 5636kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 1ms
memory: 5840kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 1ms
memory: 5716kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 1ms
memory: 5944kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 0ms
memory: 5656kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed