QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1163#731162#9522. A Simple String ProblemfhvirusMoyouSuccess!2024-11-10 22:36:022024-11-10 22:36:02

Details

Extra Test:

Wrong Answer
time: 0ms
memory: 42496kb

input:

6
cbcbab
ababcb

output:

4

result:

wrong answer 1st lines differ - expected: '6', found: '4'

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#731162#9522. A Simple String ProblemMoyouWA 347ms98272kbC++144.0kb2024-11-10 00:15:222024-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
*/