Manacher's Algorithm
(string/manacher.hpp)

• View this file on GitHub
• Last update: 2024-01-07 22:05:53+09:00
• Include: #include "string/manacher.hpp"

Description

Manacher のアルゴリズムは，文字列中の回文である部分文字列を求めるアルゴリズムである．

返り値を$A$とする．$S_i$を中心とする最大の回文の長さを$x$とすると，$A[2i] = (x + 1) / 2$．$S_iS_{i+1}$を中心とする最大の回文の長さを$x$とすると，$A[2i + 1] = x / 2$．

• vector<int> manacher(string s)
  • Manacher のアルゴリズムを実行する
  • 時間計算量: $O(n)$

Reference

• Manacher’s Algorithm - Finding all sub-palindromes in O(N)

Verified with

• test/yosupo/enumerate_palindromes.test.cpp

Code

#pragma once
#include <algorithm>
#include <string>
#include <vector>

std::vector<int> manacher(const std::string& s) {
    const int n = s.size();
    std::vector<int> vs(2 * n - 1);
    // odd length
    for (int i = 0, l = 0, r = -1; i < n; ++i) {
        int k = (i > r) ? 1 : std::min(vs[2 * (l + r - i)], r - i + 1);
        while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) ++k;
        vs[2 * i] = k;
        --k;
        if (i + k > r) {
            l = i - k;
            r = i + k;
        }
    }
    // even length
    for (int i = 1, l = 0, r = -1; i < n; ++i) {
        int k = (i > r) ? 0 : std::min(vs[2 * (l + r - i + 1) - 1], r - i + 1);
        while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) ++k;
        vs[2 * i - 1] = k;
        --k;
        if (i + k > r) {
            l = i - k - 1;
            r = i + k;
        }
    }
    return vs;
}

#line 2 "string/manacher.hpp"
#include <algorithm>
#include <string>
#include <vector>

std::vector<int> manacher(const std::string& s) {
    const int n = s.size();
    std::vector<int> vs(2 * n - 1);
    // odd length
    for (int i = 0, l = 0, r = -1; i < n; ++i) {
        int k = (i > r) ? 1 : std::min(vs[2 * (l + r - i)], r - i + 1);
        while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) ++k;
        vs[2 * i] = k;
        --k;
        if (i + k > r) {
            l = i - k;
            r = i + k;
        }
    }
    // even length
    for (int i = 1, l = 0, r = -1; i < n; ++i) {
        int k = (i > r) ? 0 : std::min(vs[2 * (l + r - i + 1) - 1], r - i + 1);
        while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) ++k;
        vs[2 * i - 1] = k;
        --k;
        if (i + k > r) {
            l = i - k - 1;
            r = i + k;
        }
    }
    return vs;
}

Back to top page