string/test/manacher.yuki3392.test.cpp

• View this file on GitHub
• Last update: 2025-11-29 14:52:59+09:00
• Problem: https://yukicoder.me/problems/no/3392

Depends on

• Longest palindromic substring enumeration (Manacher's algorithm) （回文長配列構築） (string/manacher.hpp)

Code

#define PROBLEM "https://yukicoder.me/problems/no/3392"
#include "../manacher.hpp"

#include <iostream>
using namespace std;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);

    int N;
    cin >> N;
    vector<int> A(N);
    for (auto &a : A) cin >> a;

    vector<int> D(N - 1);
    for (int i = 0; i < N - 1; ++i) D.at(i) = A.at(i + 1) - A.at(i);

    long long ret = N;
    for (auto [l, r] : enumerate_palindromes(D)) ret += (r - l + 1) / 2;

    cout << ret << '\n';
}

#line 1 "string/test/manacher.yuki3392.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/3392"
#line 2 "string/manacher.hpp"
#include <string>
#include <utility>
#include <vector>

// Manacher's Algorithm: radius of palindromes
// Input: std::string or std::vector<T> of length N
// Output: std::vector<int> of size N
// Complexity: O(N)
// Sample:
// - `sakanakanandaka` -> [1, 1, 2, 1, 4, 1, 4, 1, 2, 2, 1, 1, 1, 2, 1]
// Reference: https://snuke.hatenablog.com/entry/2014/12/02/235837
template <typename T> std::vector<int> manacher(const std::vector<T> &S) {
    std::vector<int> res(S.size());
    int i = 0, j = 0;
    while (i < int(S.size())) {
        while (i - j >= 0 and i + j < int(S.size()) and S[i - j] == S[i + j]) j++;
        res[i] = j;
        int k = 1;
        while (i - k >= 0 and i + k < int(S.size()) and k + res[i - k] < j)
            res[i + k] = res[i - k], k++;
        i += k, j -= k;
    }
    return res;
}
std::vector<int> manacher(const std::string &S) {
    std::vector<char> v(S.size());
    for (int i = 0; i < int(S.size()); i++) v[i] = S[i];
    return manacher(v);
}

// Find maximal palindrome length for each center
// input: array of length N
// output: array of length N * 2 - 1
template <typename T>
std::vector<std::pair<int, int>> enumerate_palindromes(const std::vector<T> &vec) {
    if (vec.empty()) return {};

    std::vector<T> v;
    const int N = vec.size();
    for (int i = 0; i < N - 1; i++) {
        v.push_back(vec[i]);
        v.push_back(-1);
    }
    v.push_back(vec.back());
    const auto man = manacher(v);
    std::vector<std::pair<int, int>> ret;
    for (int i = 0; i < N * 2 - 1; i++) {
        if (i & 1) {
            int w = man[i] / 2;
            ret.emplace_back((i + 1) / 2 - w, (i + 1) / 2 + w);
        } else {
            int w = (man[i] - 1) / 2;
            ret.emplace_back(i / 2 - w, i / 2 + w + 1);
        }
    }
    return ret;
}
std::vector<std::pair<int, int>> enumerate_palindromes(const std::string &S) {
    std::vector<char> v(S.size());
    for (int i = 0; i < int(S.size()); i++) v[i] = S[i];
    return enumerate_palindromes<char>(v);
}
#line 3 "string/test/manacher.yuki3392.test.cpp"

#include <iostream>
using namespace std;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);

    int N;
    cin >> N;
    vector<int> A(N);
    for (auto &a : A) cin >> a;

    vector<int> D(N - 1);
    for (int i = 0; i < N - 1; ++i) D.at(i) = A.at(i + 1) - A.at(i);

    long long ret = N;
    for (auto [l, r] : enumerate_palindromes(D)) ret += (r - l + 1) / 2;

    cout << ret << '\n';
}

Back to top page