QOJ.ac
QOJ
ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|
#1163 | #731162 | #9522. A Simple String Problem | fhvirus | Moyou | Success! | 2024-11-10 22:36:02 | 2024-11-10 22:36:02 |
詳細信息
Extra Test:
Wrong Answer
time: 0ms
memory: 42496kb
input:
6 cbcbab ababcb
output:
4
result:
wrong answer 1st lines differ - expected: '6', found: '4'
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#731162 | #9522. A Simple String Problem | Moyou | WA | 347ms | 98272kb | C++14 | 4.0kb | 2024-11-10 00:15:22 | 2024-11-10 22:38:53 |
answer
// Problem: A Simple String Problem
// Contest: Virtual Judge - Gym
// Author: Moyou
// Copyright (c) 2024 Moyou All rights reserved.
// Date: 2024-11-09 22:28:04
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
// #define int long long
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;
const int N = 4e5 + 10;
int n, m;
string s, t, S, RS;
struct SuffixArray {
int n, sa[N * 2], rk[N * 2], sa2[N * 2], x[N], buc[N], ht[N], sig, lg[N], st[20][N];
void SA(string s) {
n = s.size() - 1;
for(int i = 1; i <= n; i ++) rk[i] = s[i], sig = max(sig, rk[i]), buc[rk[i]] ++;
for(int i = 1; i <= sig; i ++) buc[i] += buc[i - 1];
for(int i = 1; i <= n; i ++) sa[buc[rk[i]] --] = i;
for(int j = 1, idx = 0; idx < n; j *= 2, sig = idx) {
idx = 0; for(int i = n - j + 1; i <= n; i ++) sa2[++ idx] = i;
for(int i = 1; i <= n; i ++) if(sa[i] > j) sa2[++ idx] = sa[i] - j;
for(int i = 1; i <= sig; i ++) buc[i] = 0;
for(int i = 1; i <= n; i ++) x[i] = rk[sa2[i]], buc[x[i]] ++;
for(int i = 1; i <= sig; i ++) buc[i] += buc[i - 1];
for(int i = n; i; i --) sa[buc[x[i]] --] = sa2[i];
idx = 1, swap(sa2, rk), rk[sa[1]] = 1;
for(int i = 2; i <= n; i ++) {
if(sa2[sa[i]] == sa2[sa[i - 1]] && sa2[sa[i] + j] == sa2[sa[i - 1] + j]) rk[sa[i]] = idx;
else rk[sa[i]] = ++ idx;
}
// cout << idx << '\n';
}
for(int i = 1, l = 0; i <= n; i ++) {
if(l) l --;
while(i + l <= n && sa[rk[i] - 1] + l <= n && s[i + l] == s[sa[rk[i] - 1] + l]) l ++;
ht[rk[i]] = l;
}
// for(int i = 1; i <= n; i ++) cout << rk[i] << ' '; cout << endl;
// for(int i = 1; i <= n; i ++) cout << ht[rk[i]] << ' '; cout << endl;
}
void ST() {
for(int i = 1; i <= n; i ++) st[0][i] = ht[i];
for(int i = 2; i <= n; i ++) lg[i] = lg[i >> 1] + 1;
for(int i = 1; i <= lg[n]; i ++)
for(int j = 1; j + (1 << i) - 1 <= n; j ++)
st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
}
int LCP(int l, int r, bool op = 0) {
if(l == r) return 0;
if(op) l = n - l + 1, r = n - r + 1;
if(l < 1 || l > n || r < 1 || r > n) return 0;
if((l = rk[l]) > (r = rk[r])) swap(l, r);
int k = lg[r - l];
return min(st[k][l + 1], st[k][r - (1 << k) + 1]);
}
} po, ro;
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> s >> t;
s += '$', t = "#" + t;
S = s + t, RS = S;
int stt = s.size();
reverse(RS.begin(), RS.end());
S = " " + S, RS = " " + RS;
po.SA(S), po.ST(), ro.SA(RS), ro.ST();
// cout << S << "\n" << RS << '\n';
// cout << po.LCP(3, 12) << '\n';
for(int len = (n + 1) / 2; len; len --) {
for(int p = 1; p <= n + 1; p += len) {
int x = po.LCP(p + stt, p + len + stt), y = ro.LCP(p - 1 + stt, stt + p + len - 1, 1);
int pos1 = p - 1 - y, pos2 = p + len - 1 - y;
int z = ro.LCP(pos1, stt + pos2, 1);
if(x + y + z >= len) return cout << len * 2, 0;
x = ro.LCP(p - 1, p + len - 1, 1), y = po.LCP(p, p + len);
pos1 = p + y, pos2 = p + len + y;
z = po.LCP(pos1, pos2 + stt);
// if(len == 3) cout << x << ' ' << y << ' ' << pos1 << ' ' << pos2 + stt << ' ' << z << '\n';
if(x + y + z >= len) return cout << len * 2, 0;
if(ro.LCP(p - 1, p + len - 1 + stt, 1) + po.LCP(p, p + len) >= len) return cout << len * 2, 0;
}
}
cout << 0 << '\n';
return 0;
}
/*
aabba$#baaba
aabba$
#baaba
a b c a b $ # a c a b c
3 7 12 9 1 5 11 4 10 2 6 8
5 9 11 3 7 2 1 6 12 4 8 10
5 9 11 3 7 2 1 6 12 4 8 10
abcab$
#acabc
*/