QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#679837 | #9522. A Simple String Problem | ucup-team4435# | AC ✓ | 441ms | 101780kb | C++20 | 8.6kb | 2024-10-26 18:51:09 | 2024-11-10 22:36:53 |
Judging History
你现在查看的是最新测评结果
- [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 18:51:09]
- 提交
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define all(a) begin(a), end(a)
#define len(a) int((a).size())
void SA_IS(const int *s, int *SA, int n, int K) {
// s 为字符串数组[0..n-1] 必须保证 s[n-1]=0 且为最小值
// SA 为存储后缀数组[0..n-1]
// n 为字符串长度
// K 为值域
bool *t = new bool[n]; // 类型数组
int *bkt = new int[K]; // 桶
int *bkt_l = new int[K];
int *bkt_r = new int[K];
int n1 = 0; // LMS-后缀的数量
int *p1; //按出现顺序存储所有 LMS-后缀的索引
#define is_S_type(x) (t[x])
#define is_L_type(x) (!t[x])
#define is_LMS_type(x) (is_S_type(x) && x != 0 && is_L_type(x - 1))
// 预处理每一个后缀的类型
t[n - 1] = true; // 0 为 S-型后缀且为 LMS-型后缀
for (int i = n - 2; i >= 0; --i) {
t[i] = (s[i] < s[i + 1] || (is_S_type(i + 1) && s[i] == s[i + 1]));
n1 += is_LMS_type(i + 1); // s[0] 必然不是 LMS-型后缀,不会影响
}
// 预处理桶的边界
for (int i = 0; i != K; ++i) bkt[i] = 0;
for (int i = 0; i != n; ++i) ++bkt[s[i]];
for (int i = 0, sum = 0; i != K; ++i) sum += bkt[i], bkt_r[i] = sum, bkt_l[i] = sum - bkt[i];
#define indecud_sort() \
do { \
for (int i = 0; i != K; ++i) bkt[i] = bkt_l[i]; \
for (int i = 0, j; i != n; ++i) \
if ((j = SA[i] - 1) >= 0 && is_L_type(j)) SA[bkt[s[j]]++] = j; \
for (int i = 0; i != K; ++i) bkt[i] = bkt_r[i]; \
for (int i = n - 1, j; i >= 0; --i) \
if ((j = SA[i] - 1) >= 0 && is_S_type(j)) SA[--bkt[s[j]]] = j; \
} while (0)
// 将所有 LMS-后缀放入 SA 对应桶的末尾并诱导排序
p1 = new int[n1];
for (int i = 0, j = 0; i != n; ++i) {
SA[i] = -1;
if (is_LMS_type(i)) p1[j++] = i;
}
for (int i = 0; i != K; ++i) bkt[i] = bkt_r[i];
for (int i = n1 - 1; i >= 0; --i) SA[--bkt[s[p1[i]]]] = p1[i];
indecud_sort();
int *s1 = new int[n1]; // 新的字符串
int *SA1 = new int[n1]; // 存储新的字符串排的后缀数组
for (int i = 0, j = 0; i != n; ++i)
if (is_LMS_type(SA[i])) SA1[j++] = SA[i]; // 存储 LMS-子串的相对顺序
int name = 0;
// 对所有 LMS-子串命名
for (int i = 0, prev = -1; i != n1; ++i) {
int pos = SA1[i];
for (int j = 0;; ++j) // 无需设置范围,因为 s[n-1]=0 为最小值且不会出现在其余位置
if (prev == -1 || s[pos + j] != s[prev + j] || is_S_type(pos + j) != is_S_type(prev + j)) {
prev = pos, ++name;
break;
} else if (j != 0 && (is_LMS_type(pos + j) || is_LMS_type(prev + j))) // 到末尾了停止比较
break;
SA[pos] = name - 1; // 利用 SA 暂时存储新字符串的 name
}
for (int i = 0; i != n1; ++i) s1[i] = SA[p1[i]];
if (name != n1)
SA_IS(s1, SA1, n1, name);
else
for (int i = 0; i != n1; ++i) SA1[s1[i]] = i;
for (int i = 0; i != K; ++i) bkt[i] = bkt_r[i];
for (int i = 0; i != n; ++i) SA[i] = -1;
for (int i = n1 - 1; i >= 0; --i) SA[--bkt[s[p1[SA1[i]]]]] = p1[SA1[i]];
indecud_sort();
delete[] SA1;
delete[] s1;
delete[] p1;
delete[] bkt_r;
delete[] bkt_l;
delete[] bkt;
delete[] t;
#undef is_S_type
#undef is_L_type
#undef is_LMS_type
#undef indecud_sort
}
std::vector<int> get_sa(const std::string &s) {
int len = s.size();
std::vector<int> SA(len + 1), s_cpy(len + 1);
for (int i = 0; i != len; ++i) s_cpy[i] = s[i];
s_cpy.back() = 0;
SA_IS(s_cpy.data(), SA.data(), len + 1, 128);
return std::vector<int>(SA.begin() + 1, SA.end());
}
struct suffix_array {
std::vector<int> order, suffix_position, lcp;
template<typename T>
suffix_array(T str = T()) {
int n = str.size() + 1;
order = get_sa(str);
order.insert(order.begin(), n - 1);
suffix_position.resize(n);
for (int i = 0; i < n; i++) {
suffix_position[order[i]] = i;
}
lcp.resize(n);
int current_lcp = 0;
for (int suffix = 0; suffix < n - 1; suffix++, current_lcp = current_lcp == 0 ? 0 : current_lcp - 1) {
int previous_suffix = order[suffix_position[suffix] - 1];
while (str[suffix + current_lcp] == str[previous_suffix + current_lcp])
current_lcp++;
lcp[suffix_position[suffix]] = current_lcp;
}
}
};
/*
* Zero based.
* Works for operations Op, such that Op(S) = Op(S \cup x), where x in S (like min, max, gcd...).
* Operation must be commutative.
*/
template<typename T, typename merge_t = std::function<T(T, T)>>
class sparse_table {
private:
std::vector<std::vector<T>> sparse;
const merge_t merge;
public:
sparse_table(const merge_t &merge) : merge(merge) {}
sparse_table(const std::vector<T> &a, const merge_t &merge) : merge(merge) {
const int n = a.size(), lg = std::__lg(std::max(1, n));
sparse.reserve(lg + 1);
sparse.push_back(a);
for (int level = 1; level <= lg; level++) {
sparse.push_back(std::vector<T>(n - (1 << level) + 1));
for (int i = 0; i < static_cast<int>(sparse[level].size()); i++) {
sparse[level][i] = merge(sparse[level - 1][i], sparse[level - 1][i + (1 << (level - 1))]);
}
}
}
sparse_table(const sparse_table &sparse) : sparse(sparse.sparse), merge(sparse.merge) {}
sparse_table& operator=(const sparse_table<T, merge_t> &another) {
sparse = another.sparse;
return *this;
}
// Returns result of merging elements on the interval [l, r).
T query(int l, int r) const {
assert(l < r);
const int level = std::__lg(r - l);
return merge(sparse[level][l], sparse[level][r - (1 << level)]);
}
};
struct LCP {
inline static auto merge_min = [](int x, int y) {
return min(x, y);
};
int n;
sparse_table<int, decltype(merge_min)> sparse;
suffix_array sa;
LCP(string s, string t) : n(len(s)), sparse(merge_min), sa(s + "#" + t) {
sparse = sparse_table<int, decltype(merge_min)>(sa.lcp, merge_min);
}
int lcp(pair<int, int> x, pair<int, int> y) {
if (x.first >= n || y.first >= n || x.first < 0 || y.first < 0) {
return 0;
}
int xi = x.first + x.second * (n + 1);
int yi = y.first + y.second * (n + 1);
auto [l, r] = minmax(sa.suffix_position[xi], sa.suffix_position[yi]);
return sparse.query(l + 1, r + 1);
}
};
int solve(int n, string s, string t) {
n++;
s.push_back('!');
t = "@" + t;
LCP forward(s, t);
auto rev_s = s;
auto rev_t = t;
reverse(all(rev_s));
reverse(all(rev_t));
LCP backward(rev_s, rev_t);
for (int length = n / 2; length >= 1; length--) {
for (int l1 = 0; l1 + 2 * length <= n; l1 += length) {
int l2 = l1 + length;
int l3 = l2 + length;
{ // case 1
int max_yellow = backward.lcp({n - 1 - (l1 + length - 1), 0}, {n - 1 - (l2 + length - 1), 1});
int max_red = forward.lcp({l2, 0}, {l3, 1});
max_red += forward.lcp({l2 + max_red, 1}, {l3 + max_red, 1});
if (max_yellow + max_red >= length) {
return length;
}
}
{ // case 2
int max_red = forward.lcp({l2, 1}, {l3, 1});
int max_yellow = backward.lcp({n - 1 - (l1 + length - 1), 1},
{n - 1 - (l2 + length - 1), 1});
max_yellow += backward.lcp({n - 1 - (l1 + length - 1 - max_yellow), 0},
{n - 1 - (l2 + length - 1 - max_yellow), 1});
if (max_yellow + max_red >= length) {
return length;
}
}
}
}
return 0;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n;
string s, t;
cin >> n >> s >> t;
int ans = solve(n, s, t);
reverse(all(s));
reverse(all(t));
ans = max(ans, solve(n, t, s));
cout << 2 * ans << '\n';
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3488kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 294ms
memory: 101284kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 298ms
memory: 101780kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 311ms
memory: 100928kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 347ms
memory: 101372kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 92ms
memory: 100948kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 101ms
memory: 101052kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 441ms
memory: 101064kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed