QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#694957 | #9522. A Simple String Problem | 中国入民小学附属信息I队 (Zicheng Wang, Shubang Liu, Minkai Shao)# | AC ✓ | 334ms | 88884kb | C++14 | 3.0kb | 2024-10-31 19:01:29 | 2024-11-10 22:38:06 |
Judging History
This is the latest submission verdict.
- [2024-11-10 22:36:11]
- hack成功,自动添加数据
- (/hack/1163)
- [2024-11-06 21:48:00]
- hack成功,自动添加数据
- (/hack/1142)
- [2024-10-31 19:01:29]
- Submitted
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 10;
struct SA
{
int sa[maxn], id[maxn], rk[maxn << 1], oldr[maxn << 1];
int tmp[maxn], lg[maxn], f[19][maxn], n;
char *sssss;
bool cmp(int i, int j, int w) { return oldr[i] == oldr[j] && oldr[i + w] == oldr[j + w]; }
void buildsa(char *s, int len)
{
n = len;
sssss = s;
int m = 127, p;
for (int i = 1; i <= n; i++) tmp[rk[i] = s[i]]++;
for (int i = 1; i <= m; i++) tmp[i] += tmp[i - 1];
for (int i = n; i; i--) sa[tmp[rk[i]]--] = i;
for (int j = 1; j < n; j <<= 1)
{
p = 0;
for (int i = n; i > n - j; i--) id[++p] = i;
for (int i = 1; i <= n; i++)
if (sa[i] > j) id[++p] = sa[i] - j;
for (int i = 0; i <= m; i++) tmp[i] = 0;
for (int i = 1; i <= n; i++) tmp[rk[i]]++;
for (int i = 1; i <= m; i++) tmp[i] += tmp[i - 1];
for (int i = n; i; i--) sa[tmp[rk[id[i]]]--] = id[i];
for (int i = 1; i <= n; i++) oldr[i] = rk[i]; p = 0;
for (int i = 1; i <= n; i++)
rk[sa[i]] = cmp(sa[i], sa[i - 1], j) ? p : ++p;
if (p == n) break;
m = p;
}
for (int i = 1, k = 0; i <= n; i++)
{
if (k) k--;
while (s[i + k] == s[sa[rk[i] - 1] + k]) k++;
f[0][rk[i]] = k;
}
for (int i = 1, k = 0; i <= n; i++)
{
if (i == (1 << (k + 1))) k++;
lg[i] = k;
}
for (int i = 1; i <= 18; i++)
for (int j = 1; j + (1 << i) - 1 <= n; j++)
f[i][j] = min(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
}
int query(int l, int r)
{
l = rk[l], r = rk[r];
if (l > r) swap(l, r); l++;
int k = lg[r - l + 1];
return min(f[k][l], f[k][r - (1 << k) + 1]);
}
}S, T;
int n;
char str1[maxn], str2[maxn], s[maxn], t[maxn];
int Lcp(int x, int y) { if (x <= 0 || y > n * 2 + 1) return 0; return S.query(x, y); }
int Lcs(int x, int y) { if (x <= 0 || y > n * 2 + 1) return 0; return T.query(2 * n + 2 - x, 2 * n + 2 - y); }
int main()
{
ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> s + 1 >> t + 2;
t[1] = s[1], s[n + 1] = t[n + 1]; n++;
for (int i = 1; i <= n; i++) str1[i] = s[i], str2[i] = t[n - i + 1];
str1[n + 1] = str2[n + 1] = '#';
for (int i = 1; i <= n; i++) str1[i + n + 1] = t[i], str2[i + n + 1] = s[n - i + 1];
str1[n * 2 + 2] = str2[n * 2 + 2] = 0;
S.buildsa(str1, 2 * n + 1), T.buildsa(str2, 2 * n + 1);
for (int len = n / 2; len; len--)
for (int r = len << 1; r <= n; r += len)
{
int l = r - len + 1;
int lcp = Lcp(l + n + 1, r + n + 2), lcs = Lcs(l + n, r + n + 1);
if (lcp + lcs + Lcs(l - lcs - 1, r - lcs + n + 1) >= len) return cout << (len << 1) << "\n", 0;
lcs = Lcs(l - 1, r), lcp = Lcp(l, r + 1);
if (lcp + lcs + Lcp(l + lcp, r + lcp + n + 2) >= len) return cout << (len << 1) << "\n", 0;
lcp = Lcp(l, r + n + 2), lcs = Lcs(l - 1, r + n + 1);
if (lcp + lcs + max(Lcp(l + lcp + n + 1, r + n + 2 + lcp), Lcs(l - lcs - 1, r - lcs)) >= len) return cout << (len << 1) << "\n", 0;
}
cout << "0";
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 38488kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 0ms
memory: 38492kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 0ms
memory: 34400kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 38416kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 0ms
memory: 34384kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 38400kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 201ms
memory: 88764kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 181ms
memory: 88356kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 200ms
memory: 88584kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 334ms
memory: 88308kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 142ms
memory: 88204kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 157ms
memory: 88188kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 295ms
memory: 88884kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 0ms
memory: 40524kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 0ms
memory: 44632kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 0ms
memory: 44672kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 0ms
memory: 44548kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 0ms
memory: 36488kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 2ms
memory: 34312kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 3ms
memory: 50700kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 0ms
memory: 46664kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed