QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#680973 | #9522. A Simple String Problem | ucup-team191# | AC ✓ | 716ms | 79512kb | C++23 | 4.1kb | 2024-10-26 23:54:23 | 2024-10-28 14:30:43 |
Judging History
你现在查看的是测评时间为 2024-10-28 14:30:43 的历史记录
- [2024-11-10 22:36:11]
- hack成功,自动添加数据
- (/hack/1163)
- [2024-11-06 21:48:00]
- hack成功,自动添加数据
- (/hack/1142)
- [2024-10-28 15:17:17]
- hack成功,自动添加数据
- (/hack/1080)
- [2024-10-28 14:28:57]
- hack成功,自动添加数据
- (/hack/1079)
- [2024-10-27 18:36:42]
- hack成功,自动添加数据
- (/hack/1075)
- [2024-10-26 23:54:23]
- 提交
answer
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)
#define sz(a) ((int)(a).size())
#define rep(i, a, b) for(int i = (a);(i) < (b);(i)++)
const int N=300010,MOD=1e9+7;
const char en='\n';
const ll LLINF=1ll<<60;
const int LG = 19;
struct RMQ {
vi lvl[LG];
RMQ() {}
RMQ(vi &v) {
lvl[0] = v;
lvl[0].erase(lvl[0].begin());
int n = (int)v.size();
for(int j = 1;j < LG;j++) {
lvl[j].resize(n);
for(int i = 0;i < n;i++) {
lvl[j][i] = min(lvl[j - 1][i], lvl[j - 1][min(i + (1 << (j - 1)), n - 1)]);
}
}
}
int get_min(int i, int j) {
int val = __lg(j - i + 1);
//cout << i << " " << j << " " << val << " " << min(lvl[val][i], lvl[val][j - (1 << val) + 1]) << endl;
return min(lvl[val][i], lvl[val][j - (1 << val) + 1]);
}
};
struct SuffixArray {
vi sa, lcp, inv;
RMQ M;
SuffixArray() {}
SuffixArray(string &s, int lim=256) {
int n = sz(s) + 1, k = 0, a, b;
vi x(all(s) + 1), y(n), ws(max(n, lim)), rank(n);
inv.resize(n + 1);
sa = lcp = y, iota(all(sa), 0);
for (int j = 0, p = 0; p < n; j = max(1, j * 2), lim = p) {
p = j, iota(all(y), n - j);
rep(i, 0, n) if (sa[i] >= j) y[p++] = sa[i] - j;
fill(all(ws), 0);
rep(i,0,n) ws[x[i]]++;
rep(i,1,lim) ws[i] += ws[i - 1];
for (int i = n; i--;) sa[--ws[x[y[i]]]] = y[i];
swap(x, y), p = 1, x[sa[0]] = 0;
rep(i,1,n) a = sa[i - 1], b = sa[i], x[b] =
(y[a] == y[b] && y[a + j] == y[b + j]) ? p - 1 : p++;
}
rep(i, 1, n) rank[sa[i]] = i;
for (int i = 0, j; i < n - 1; lcp[rank[i++]] = k)
for (k && k--, j = sa[rank[i] - 1];
s[i + k] == s[j + k]; k++);
rep(i, 0, n) inv[sa[i]] = i;
M = RMQ(lcp);
}
int get_lcp(int i, int j) {
i = inv[i], j = inv[j];
return M.get_min(min(i, j), max(i, j) - 1);
}
};
int n;
string s1, s2;
SuffixArray Sa, Ra;
// i je fiksan, j mora biti gore
int fuzzy_lcp(int i, int j, SuffixArray &S = Sa) {
if(i < 0 || i == n || i > 2 * n) return 0;
if(j < 0 || j == n || j > 2 * n) return 0;
assert(j < n);
int x = S.get_lcp(i, j);
int y = S.get_lcp(i + x, j + x + n);
return x + y;
}
int fuzzy_lcs(int i, int j) {
assert(j >= n);
return fuzzy_lcp(2 * n - i, 2 * n - j, Ra);
}
bool check(int k) {
for(int i = 0;i + k - 1 < n;i += k) {
int lft = Ra.get_lcp(2 * n - i, 2 * n - ((n + 1) + (i + k - 1)));
int rig = fuzzy_lcp((n + 1) + (i + k - 1), i);
if(lft + rig >= k + 1 && s1[i] == s2[i + k - 1]) {
//cout << lft << " " << rig << endl;
//cout << i << endl;
//cout << 1 << endl;
return true;
}
lft = fuzzy_lcs(i, (n + 1) + (i + k - 1));
rig = Sa.get_lcp((n + 1) + (i + k - 1), i);
if(lft + rig >= k + 1 && s1[i] == s2[i + k - 1]) {
//cout << lft << " " << rig << endl;
//cout << i << endl;
//cout << 1 << endl;
return true;
}
lft = Sa.get_lcp(i, i + k);
rig = Ra.get_lcp(2 * n - (i - 1), 2 * n - (i + k - 1));
if(lft + rig >= k) {
//cout << 2 << endl;
return true;
}
lft = Sa.get_lcp((n + 1) + i, (n + 1) + i + k);
rig = Ra.get_lcp(2 * n - (i - 1) - (n + 1), 2 * n - (i + k - 1) - (n + 1));
if(lft + rig >= k) {
//cout << lft << " " << rig << endl;
//cout << i << " " << 3 << endl;
return true;
}
lft = Ra.get_lcp(2 * n - (i - 1), 2 * n - (i + k - 1));
rig = fuzzy_lcp(i, i + k);
if(lft + rig >= k) {
//cout << 4 << endl;
return true;
}
lft = fuzzy_lcs((n + 1) + (i + k - 1), (n + 1) + (i - 1));
rig = Sa.get_lcp((n + 1) + i, (n + 1) + i + k);
if(lft + rig >= k) {
//cout << lft << " " << rig << endl;
//cout << i << " " << 5 << endl;
return true;
}
}
return false;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> s1 >> s2;
string S = s1 + "*" + s2;
string RS = S;
reverse(RS.begin(), RS.end());
Sa = SuffixArray(S);
Ra = SuffixArray(RS);
int ans = n;
//printf("%d\n", check(3));
//return 0;
while(ans > 0 && !check(ans)) ans--;
cout << 2 * ans << endl;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3836kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 241ms
memory: 79384kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 222ms
memory: 79348kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 259ms
memory: 79400kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 681ms
memory: 79512kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 209ms
memory: 79460kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 219ms
memory: 79396kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 716ms
memory: 79332kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3820kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3612kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3832kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 1ms
memory: 3792kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed