let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

PALINY - Palindrome dài nhất

Sử dụng thuật toán Manacher.

main.cpp
Open in Github Download
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int manacher(const string &s) {
    string a;
    for (char c: s) a += '.', a += c;
    a += '.';
    int n = a.size();

    vector<int> f(n);
    int r = 0, c = 0;

    for (int i=0; i<n; i++) {
        f[i] = i<r? min(r-i, f[c-(i-c)]) : 0;
        while (a[i-f[i]-1] == a[i+f[i]+1]) f[i]++;
        if (i+f[i] > r) {
            r = i + f[i];
            c = i;
        }
    }

    return *max_element(f.begin(), f.end());
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    string s; cin >> s;
    cout << manacher(s);
    return 0;
}
Comments