Spaghetti Source logo

最長回文 (Manacher)

説明

回文とは text == reverse(text) を満たす文字列のことをいう.与えられた文字列の中で,最も長い部分回文を求める問題を最長回文問題という.

この問題は最近では Suffix Tree / Array の応用問題として取り上げられることが多い( text $ reverse(text) の Suffix Tree を作る).しかし,Manacher によるもっとシンプルな解法が古くから知られている.

簡単のため,長さ奇数の回文のみを考える.rad[i] で text[i] を中心とする回文の半径を表すことにする.このとき,次の定理が成立する.

Thm. rad[i-k] ≠ rad[i] - k ならば rad[i+k] = min(rad[i-k], rad[i] - k)

証明は絵を描けば簡単にわかる.要するに i の前後 rad[i] に関して i+k の状況はほぼ i-k と同じで,rad[i] をはみ出す部分で対称性が崩れる,というだけである.

長さ偶数の回文についても同様の定理が成立するが,実装ではもっと簡単に,各文字間にダミーの文字を挟んでやればいい.このときダミー文字中心の奇数長回文を求めることがもとの文字列の偶数長回文を求めることに対応する.

計算量

使い方

int longest_palindrome(char *text, int n)
長さ n の文字列 text の最長回文の長さを返す.返しているポインタの位置は,最長回文の中心である.

ソースコード

int longest_palindrome(char *text, int n) {
  int rad[2*n], i, j, k;
  for (i = 0, j = 0; i < 2*n; i += k, j = max(j-k, 0)) {
    while (i-j >= 0 && i+j+1 < 2*n && text[(i-j)/2] == text[(i+j+1)/2]) ++j;
    rad[i] = j;
    for (k = 1; i-k >= 0 && rad[i]-k >= 0 && rad[i-k] != rad[i]-k; ++k)
      rad[i+k] = min(rad[i-k], rad[i]-k);
  }
  return *max_element(rad, rad+2*n); // ret. centre of the longest palindrome
}

Verified

参考文献

前原 貴憲(maehara@prefield.com).

Last Modified: 2007.10.27 10:55:31.