QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#734934 | #9522. A Simple String Problem | winsun | AC ✓ | 539ms | 79668kb | C++14 | 4.0kb | 2024-11-11 16:07:28 | 2024-11-11 16:07:29 |
Judging History
answer
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <utility>
#define fi first
#define se second
using namespace std;
typedef long long LL;
template <typename Tp> inline void read(Tp& x) {
char ch; bool op = 0; x = 0;
do ch = getchar(), op |= ch == '-'; while (ch < '0' || ch > '9');
do x = (x<<3)+(x<<1)+(ch&15), ch = getchar(); while (ch >= '0' && ch <= '9');
if (op) x = -x;
}
bool Mst;
const int MAXN = 4e5+5;
int lg[MAXN];
class SA {
private:
int sa[MAXN], rk[MAXN], cnt[MAXN], tmp[MAXN];
int st[MAXN][20];
int n, m;
void rsort() {
for (int i = 1; i <= m; ++i) cnt[i] = 0;
for (int i = 1; i <= n; ++i) ++cnt[rk[i]];
for (int i = 1; i <= m; ++i) cnt[i] += cnt[i-1];
for (int i = n; i; --i) sa[cnt[rk[tmp[i]]]--] = tmp[i];
}
public:
char str[MAXN];
void calc() {
n = strlen(str + 1), m = 127;
// puts(str + 1);
for (int i = 1; i <= n; ++i) rk[i] = str[i], tmp[i] = n-i+1;
rsort();
for (int k = 1; k == 1 || m < n; k <<= 1) {
int x = 0;
for (int i = 1; i <= k; ++i) tmp[++x] = n - i + 1;
for (int i = 1; i <= n; ++i) if (sa[i] > k) tmp[++x] = sa[i] - k;
rsort();
for (int i = 1; i <= n; ++i) tmp[i] = rk[i];
auto cmp = [&](int x, int y) {
if (tmp[x] != tmp[y]) return 1;
if (x + k <= n && y + k <= n) return int(tmp[x+k] != tmp[y+k]);
return 1;
};
rk[sa[1]] = m = 1;
for (int i = 2; i <= n; ++i) rk[sa[i]] = m += cmp(sa[i-1], sa[i]);
}
// for (int i = 1; i <= n; ++i) printf("%d ", sa[i]); puts("");
for (int i = 1, x = 0; i <= n; ++i) {
if (rk[i] == 1) { st[rk[i]][0] = x = 0; continue; }
if (x) --x;
for (int j = sa[rk[i]-1]; i+x <= n && j+x <= n && str[i+x] == str[j+x]; ++x);
st[rk[i]][0] = x;
}
for (int k = 1; 1 << k <= n; ++k) {
for (int l = 1; l <= n - (1<<k) + 1; ++l) {
st[l][k] = min(st[l][k-1], st[l+(1<<k-1)][k-1]);
}
}
}
int query(int x, int y) {
if (rk[x] > rk[y]) swap(x, y);
int l = rk[x] + 1, r = rk[y], len = r - l + 1, k = lg[len];
// printf("%d %d %d\n", l, r, k);
return min(st[l][k], st[r-(1<<k)+1][k]);
}
} ori, rev;
int n;
char a[MAXN], b[MAXN];
int solve() {
for (int k = n + 1 >> 1; k; --k) {
for (int p = 1, q, lcp, lcs; p <= n - k + 1; p += k) {
q = p + k;
lcp = ori.query(p, q), lcs = rev.query(n-p+2, n-q+2);
lcp += ori.query(p+lcp, n+1 +q+lcp);
// printf("%d %d %d %d\n", p, q, lcp, lcs);
if (lcp + lcs >= k) return k;
lcp = ori.query(p, n+1 +q), lcs = rev.query(n-p+2, n+1 +n-q+2);
// printf("%d %d %d %d\n", p, q, lcp, lcs);
if (lcp + lcs >= k) return k;
lcp = ori.query(n+1 +p, n+1 +q), lcs = rev.query(n+1 +n-p+2, n+1 +n-q+2);
lcs += rev.query(n-p+2+lcs, n+1 +n-q+2+lcs);
// printf("%d %d %d %d\n", p, q, lcp, lcs);
if (lcp + lcs >= k) return k;
}
}
return 0;
}
bool Med;
int main() {
#ifndef ONLINE_JUDGE
freopen("qoj9522.in", "r", stdin);
freopen("qoj9522.out", "w", stdout);
fprintf(stderr, "%.3lfMB\n", (&Mst - &Med) / 1048576.0);
#endif
lg[1] = 0;
for (int i = 2; i <= 4e5+1; ++i) lg[i] = lg[i>>1] + 1;
read(n), ++n, scanf("%s%s", a+1, b+2);
a[n] = '#', b[1] = '@';
// printf("%s %s\n", a+1, b+1);
for (int i = 1; i <= n; ++i) {
ori.str[i] = a[i], ori.str[i+n+1] = b[i];
rev.str[n-i+1] = a[i], rev.str[n-i+1+n+1] = b[i];
}
ori.str[n+1] = rev.str[n+1] = '$';
ori.calc(), rev.calc();
printf("%d\n", solve() << 1);
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 20960kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 3ms
memory: 20172kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 0ms
memory: 19100kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 19224kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 0ms
memory: 18420kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 21616kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 247ms
memory: 79668kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 235ms
memory: 79284kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 247ms
memory: 79348kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 539ms
memory: 79284kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 209ms
memory: 79356kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 226ms
memory: 79372kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 377ms
memory: 79276kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 0ms
memory: 21604kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 0ms
memory: 21624kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 3ms
memory: 20784kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 0ms
memory: 20876kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 0ms
memory: 19028kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 0ms
memory: 20864kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 3ms
memory: 19200kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 3ms
memory: 21584kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed