QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#688588 | #9522. A Simple String Problem | wtz2333 | AC ✓ | 991ms | 155732kb | C++14 | 4.6kb | 2024-10-30 11:17:15 | 2024-10-30 11:17:16 |
Judging History
你现在查看的是测评时间为 2024-10-30 11:17:16 的历史记录
- [2024-11-10 22:36:11]
- hack成功,自动添加数据
- (/hack/1163)
- [2024-11-06 21:48:00]
- hack成功,自动添加数据
- (/hack/1142)
- [2024-10-30 11:17:15]
- 提交
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 7;
const int SIGMA_SIZE = 128;
struct SuffixArray{
int sa[maxn], S[maxn], rnk[maxn], tax[maxn], tp[maxn], height[maxn];
int h[22][maxn];
int n;
int m = SIGMA_SIZE;
void SA(string s) {
int n = s.size();
s = '#' + s;
int m = SIGMA_SIZE;
memset(tax,0,sizeof tax);
auto RadixSort = [&]() {
for (int i = 0; i <= m; ++i) tax[i] = 0;
for (int i = 1; i <= n; ++i) ++tax[rnk[i]];
for (int i = 1; i <= m; ++i) tax[i] += tax[i - 1];
for (int i = n; i; --i) sa[tax[rnk[tp[i]]]--] = tp[i];
};
for (int i = 1; i <= n; ++i) {
S[i] = s[i] - '0';
tp[i] = i;
rnk[i] = S[i];
}
RadixSort();
for (int len = 1, p = 0; p != n; m = p, len <<= 1) {
p = 0;
for (int i = n - len + 1; i <= n; ++i) tp[++p] = i;
for (int i = 1; i <= n; ++i) if (sa[i] > len) tp[++p] = sa[i] - len;
RadixSort();
std::swap(rnk, tp);
p = 0;
for (int i = 1; i <= n; ++i)
rnk[sa[i]] = ((tp[sa[i]] == tp[sa[i-1]]) && (tp[sa[i] + len] == tp[sa[i-1] + len])) ? p : ++p;
}
for (int i = 1, p = 0; i <= n; ++i) {
int pre = sa[rnk[i] - 1];
if (p) --p;
while (S[pre + p] == S[i + p]) ++p;
h[0][rnk[i]] = height[rnk[i]] = p;
}
for (int i = 1; i <= 20; ++i) {
memset(h[i], 0x3f, n * 4 + 4);
for (int j = 1; j + (1 << i - 1) <= n; ++j)
h[i][j] = min(h[i - 1][j], h[i - 1][j + (1 << i - 1)]);
}
}
int Q(int l, int r) {
if (l > r) swap(l, r);
++l;
int k = __lg(r - l + 1);
return min(h[k][l], h[k][r - (1 << k) + 1]);
}
int lcp(int i, int j) {
if (i == j) return n - i + 1;
return Q(rnk[i], rnk[j]);
}
}sa;
int solve(int n,string s,string t) {
string S = s,T = t;
reverse(S.begin(),S.end());
reverse(T.begin(),T.end());
string tmp = s + '1' + '2' + S + '3' + t + T + '4';
sa.SA(tmp);
// cerr << tmp << endl;
// cerr << s << "#\n";
// cerr << "#" << t << "\n";
// // 1 - n
auto lcp = [&](int op1,int op2,int i,int j) {
if(i > n || j > n || i < 1 || j < 1) return 0;
if(op1) i += 2 * n;
if(op2) j += 2 * n;
int ans = sa.lcp(i,j);
if(op1) ans = min(ans,3 * n - i + 1);
else ans = min(ans,n - i + 1);
if(op2) ans = min(ans,3 * n - j + 1);
else ans = min(ans,n - j + 1);
return ans;
};
auto lcs = [&](int op1,int op2,int i,int j) {
if(i > n || j > n || i < 1 || j < 1) return 0;
i = n - i + 1;
j = n - j + 1;
i += n;
j += n;
if(op1) i += 2 * n;
if(op2) j += 2 * n;
int ans = sa.lcp(i,j);
if(op1) ans = min(ans,4 * n - i + 1);
else ans = min(ans,2 * n - i + 1);
if(op2) ans = min(ans,4 * n - j + 1);
else ans = min(ans,2 * n - j + 1);
return ans;
};
int mx = 0;
for(int x = 1;x <= n;x ++) {
for(int y = 1;y + x - 1 <= n;y += x) {
int l = y,r = y + x - 1;
{
int k = r + lcp(1,1,l,r + 1);
int j = l - lcs(1,1,l - 1,r);
int i = j - lcs(0,1,j - 1,j - 1 + x);
if(k - i + 1 >= 2 * x) {
// cerr << x << " " << l << " " << r << endl;
mx = x;
break;
}
}
{
int t1 = lcp(0,1,l,r + 1);
int k = t1 ? r + t1 + lcp(1,1,l + t1,r + t1 + 1) : r;
int t2 = lcs(0,1,l - 1,r);
int i = t2 ? l - t2 - lcs(0,0,l - t2 - 1,r - t2) : l;
if(k - i + 1 >= 2 * x) {
// cerr << t1 << " " << t2 << endl;
// cerr << x << " " << l << " " << r << " " << i << " " << k << endl;
mx = x;
break;
}
}
}
}
return mx;
// return 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
n ++;
string s,t,S,T;
cin >> s >> t;
S = s,T = t;
reverse(S.begin(),S.end());
reverse(T.begin(),T.end());
// cout << solve(n,T,S) << endl;
cout << max(solve(n,s,t),solve(n,T,S)) * 2 << "\n";
}
// [ | . | ]
// [ | | ]
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 72176kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 8ms
memory: 73408kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 0ms
memory: 72424kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 15ms
memory: 72476kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 11ms
memory: 72332kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 8ms
memory: 73840kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 991ms
memory: 154096kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 776ms
memory: 152756kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 768ms
memory: 154668kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 709ms
memory: 153544kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 687ms
memory: 155200kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 745ms
memory: 155732kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 407ms
memory: 155160kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 8ms
memory: 72372kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 7ms
memory: 73252kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 18ms
memory: 74196kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 20ms
memory: 73076kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 8ms
memory: 72892kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 3ms
memory: 72092kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 8ms
memory: 72724kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 11ms
memory: 72832kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed