ei1333's page

ホーム > Wiki

Manacher

説明

ある文字列 $S$ が与えられているとする。Manacher では, それぞれの $i$ について文字 $i$ を中心とする最長回文の半径を記録した配列を線形時間で構築するアルゴリズムである。

具体例を以下に示す。例えば $i = 6$ を中心とする最長回文は "aba" つまり $2$ である。

abaaababa
121412321

計算量

$O(|S|)$

実装例

Manacharよりも Manachan の方が可愛いので Manachan にしてあります(?)

struct Manachan
{
  vector< int > radius;

  void build(const string &s)
  {
    radius.resize(s.size());

    int i = 0, j = 0;
    while(i < s.size()) {
      while(i - j >= 0 && i + j < s.size() && s[i - j] == s[i + j]) {
        ++j;
      }
      radius[i] = j;
      int k = 1;
      while(i - k >= 0 && i + k < s.size() && k + radius[i - k] < j) {
        radius[i + k] = radius[i - k];
        ++k;
      }
      i += k;
      j -= k;
    }
  }

  int operator[](const int k) const
  {
    return (radius[k]);
  }

  size_t size()
  {
    return (radius.size());
  }
};

問題例

参考資料