はじめに

「回文」という言葉遊びがあります。
前から読んでも、後ろから読んでも、同じ言葉になる文章のことです。

「新聞紙（しんぶんし）」などが有名ですが、長いものや面白いものもたくさん見つかっています。
わたしが以前思いついたのは、「この子もコモ湖の子（このこもこもこのこ）」でした。
コモ湖というのは、イタリア北部にある、大きな湖のことです。

今回は、任意の文字列から回文を探し、その最長のものを効率よく探す方法を考えます。

素朴な方法

たとえば、奇数長の回文を素直に調べるなら、以下を繰り返すことで可能です。

1. 0文字目から最後の文字まで、注目する文字（$i 文字目）を1つ決める
2. $i 文字目から、前後 $j 文字目を比較し、一致したら $j を1ずつ増やしていく

（偶数長の回文を調べる場合は、各文字の間に # などの文字を挟むことで、奇数長と同じやり方で調べられます）

<?php
$string = 'abacabadabacaba';  // 調べたい文字列
$result = array_fill(0, strlen($string), 0);
for($i=0; $i<strlen($string); $i++) {
    for($j=0; (0<=$i-$j) && ($i+$j<strlen($string)); $j++) {
        if($string[$i-$j]===$string[$i+$j]) {
            $result[$i] = $j+1;
        }else{
            break;
        }
    }
}
echo implode(' ', $result).PHP_EOL;
// 出力： 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1

しかし、このような全探索は、最悪 O(N^2) の計算量がかかってしまいます。
たとえば、10万文字を超えるような、長い文字列を扱いたい場合は、処理に膨大な時間がかかってしまいます。

このような場合に使えるのが、 Manacher’s Algorithm です。

アメリカの計算機科学者 G.K.Manacher 氏が考案したアルゴリズムです。

実装

文字列の頭良い感じの線形アルゴリズムたち２ という記事を参考に、 PHP で実装したものがこちらです：

<?php
function manacher (string $str):array {
    $r = [];
    $len = strlen($str);
    $i=0;
    $j=0;
    while($i<$len){
        while(0<=$i-$j && $i+$j<$len && $str[$i-$j]===$str[$i+$j]) {
            $j += 1;
        }
        $r[$i] = $j;
        $k = 1;
        while(0<=$i-$k && $k+$r[$i-$k]<$j) {
            $r[$i+$k] = $r[$i-$k];
            $k += 1;
        }
        $i += $k;
        $j -= $k;
    }
    return $r;
}
// 使い方
$str = 'abacabadabacaba';
echo implode(' ', manacher($str)).PHP_EOL;
// 出力： 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1

このアルゴリズムの要点は、ある回文が見つかったとき、左右対称なので、「左半分の回文長さが分かっていれば、右半分はそれを書き移すだけで良い」というところにあります。

一見すると、 while が二重になっているので、計算量が O(N^2) のままのように見えますが、 $i 自体が $k によってスキップされるので、 O(N) になるようです。

このような計算量の改善は、短い文章であれば、大した差ではないかもしれませんが、膨大な量の文字列を探索する場合には、劇的な差になります。

まとめ

実用上、長大な文字列の中にある回文を探すことは、無いかもしれません。
（特定の分野では、たとえば生物学で DNA 配列を解析するときに、パリンドローム配列（回文配列）を探すことに使われるそうです）

しかし、 Manacher’s Algorithm は、基本的なアイディアとしては、すでに調べた内容を記憶させ、無用な再計算をスキップするというものであり、生成 AI によって計算資源が枯渇しがちな現代においても、いろいろな気付きを与えてくれる、手ごろなアルゴリズムなのではないかと思いました。