QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#747437 | #9522. A Simple String Problem | complexor | AC ✓ | 406ms | 83052kb | C++20 | 4.5kb | 2024-11-14 17:10:06 | 2024-11-14 17:10:11 |
Judging History
answer
#include <bits/stdc++.h>
typedef unsigned long long ULL;
typedef std::pair<int, int> pii;
#define fi first
#define se second
#define MP std::make_pair
#define clr(f, n) memset(f, 0, (n) << 2)
#define cpy(f, g, n) memcpy(f, g, (n) << 2)
#define reve(f, n) std::reverse(f, (f) + (n))
int read()
{
int s = 0; int f = 1;
char c = getchar();
while (!(c >= '0' && c <= '9'))
f ^= (c == '-'), c = getchar();
while (c >= '0' && c <= '9')
s = s * 10 + (c ^ 48), c = getchar();
return f ? s : -s;
}
const int MAXN = 200005, inf = 0x3f3f3f3f, MAXV = 600005;
template<typename T> T& Fmax(T& x, T y){ return x = x < y ? y : x; };
template<typename T> T& Fmin(T& x, T y){ return x = x < y ? x : y; };
int n, lg[MAXN << 1];
char s[2][MAXN];
struct A_string_data_structure
{
int sa[MAXN << 1], rnk[MAXN << 1], ht[MAXN << 1], n, nn, st[20][MAXN << 1];
bool rev;
char s[MAXN << 1];
void suffix_sort()
{
static int cnt[MAXN << 1], id[MAXN << 1], oldrk[MAXN << 1];
clr(cnt, 200);
for (int i = 1; i <= nn; i++) cnt[s[i]]++;
for (int i = 1; i < 200; i++) cnt[i] += cnt[i - 1];
for (int i = 1; i <= nn; i++) sa[cnt[s[i]]--] = i;
rnk[sa[1]] = 1;
for (int i = 2; i <= nn; i++)
rnk[sa[i]] = rnk[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);
int V = rnk[sa[nn]];
auto cmp = [=](int i, int j, int w)->bool{
if (oldrk[i] != oldrk[j]) return false;
return (i > nn - w && j > nn - w) || (i <= nn - w && j <= nn - w && oldrk[i + w] == oldrk[j + w]);
};
// for (int i = 1; i <= nn; i++)
// printf("%d: %d %d\n", i, sa[i], rnk[i]);
for (int w = 1; V < nn; w <<= 1, V = rnk[sa[nn]])
{
int cur = 0;
for (int i = nn; i > nn - w; i--) id[++cur] = i;
for (int i = 1; i <= nn; i++)
if (sa[i] > w) id[++cur] = sa[i] - w;
clr(cnt + 1, V);
for (int i = 1; i <= nn; i++) cnt[rnk[id[i]]]++;
for (int i = 1; i <= V; i++) cnt[i] += cnt[i - 1];
for (int i = nn; i; i--) sa[cnt[rnk[id[i]]]--] = id[i];
cpy(oldrk + 1, rnk + 1, nn), rnk[sa[1]] = 1;
for (int i = 2; i <= nn; i++)
rnk[sa[i]] = rnk[sa[i - 1]] + !cmp(sa[i], sa[i - 1], w);
}
}
void gen_height()
{
for (int i = 1, j = 0; i <= nn; i++)
{
if (j) j--;
if (rnk[i] == nn) continue;
int ii = sa[rnk[i] + 1];
while (i + j <= nn && ii + j <= nn && s[i + j] == s[ii + j]) ++j;
ht[rnk[i]] = j;
}
}
#define pw(x) (1 << (x))
void gen_sparse_table()
{
cpy(st[0] + 1, ht + 1, nn);
for (int i = 1; i <= lg[nn]; i++)
for (int j = 1; j + pw(i) - 1 <= nn; j++)
st[i][j] = std::min(st[i - 1][j], st[i - 1][j + pw(i - 1)]);
}
int query(int l, int r)
{
l = rnk[l], r = rnk[r];
if (l == r) return -1;
if (l > r) std::swap(l, r);
int len = lg[r - l];
return std::min(st[len][l], st[len][r - pw(len)]);
}
#undef pw
void init(int _n, char str[2][MAXN], bool _r)
{
n = _n, nn = n << 1;
memcpy(s + 1, str[0] + 1, n);
memcpy(s + n + 1, str[1] + 1, n);
if (rev = _r) reve(s + 1, n), reve(s + n + 1, n);
suffix_sort(), gen_height(), gen_sparse_table();
// printf("%s\n", s + 1);
// for (int i = 1; i <= nn; i++)
// printf("%d: %d %d %d\n", i, sa[i], rnk[i], ht[i]);
}
int q_same(int o, int l, int r)
{
if (rev) l = n + 1 - l, r = n + 1 - r;
if (l > n || r > n) return 0;
return query(l + o * n, r + o * n);
}
int q_dif(int l, int r)
{
if (rev) l = n + 1 - l, r = n + 1 - r;
if (l > n || r > n) return 0;
return query(l, r + n);
}
} pre, suf;
int main()
{
n = read() + 1;
scanf("%s", s[0] + 1), s[0][n] = '$';
scanf("%s", s[1] + 2), s[1][1] = '@';
for (int i = 2; i <= n * 2; i++) lg[i] = lg[i >> 1] + 1;
pre.init(n, s, 1);
// printf("%s\n%s\n", s[0] + 1, s[1] + 1);
// printf("%d\n", pre.q_dif(3, 6));
suf.init(n, s, 0);
for (int len = n / 2; len; len--)
for (int i = 1, ii = len + 1; ii <= n; ii += len, i += len)
{
int lenl = pre.q_same(0, i - 1, ii - 1), lenr = suf.q_same(0, i, ii);
if (lenl + lenr + suf.q_dif(i + lenr, ii + lenr) >= len) return printf("%d\n", len * 2), 0;
lenl = pre.q_same(1, i - 1, ii - 1), lenr = suf.q_same(1, i, ii);
if (lenl + lenr + pre.q_dif(i - lenl - 1, ii - lenl - 1) >= len) return printf("%d\n", len * 2), 0;
lenl = pre.q_dif(i - 1, ii - 1), lenr = suf.q_dif(i, ii);
if (lenl + lenr + pre.q_same(0, i - lenl - 1, ii - lenl - 1) >= len) return printf("%d\n", len * 2), 0;
if (lenl + lenr + suf.q_same(1, i + lenr, ii + lenr) >= len) return printf("%d\n", len * 2), 0;
}
printf("0\n");
return 0;
}
/*
5
abcab
acabc
6
*/
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 30512kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 3ms
memory: 30428kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 0ms
memory: 26340kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 30432kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 0ms
memory: 32624kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 30428kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 240ms
memory: 80952kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 226ms
memory: 83052kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 248ms
memory: 81052kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 406ms
memory: 80736kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 197ms
memory: 82896kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 204ms
memory: 82804kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 314ms
memory: 82968kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 0ms
memory: 34520kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 3ms
memory: 36568kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 0ms
memory: 38664kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 0ms
memory: 38768kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 0ms
memory: 32556kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 0ms
memory: 30436kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 0ms
memory: 44756kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 0ms
memory: 40732kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed