回文とは、始めから読んでも終わりから読んでも同じ文字列のことです。回文には abaのようなものとabbaのようなものがあります。いまは奇数長の回文のみを考えます。
文字列 s のi番目の文字を中心とする回文が存在し、その長さをnとしたとき、(n + 1) / 2をi番目の文字を中心とする最長回文半径と定義します。
Manacherのアルゴリズムを用いることで文字列の各位置を中心とする最長回文半径を線形時間で求められるようになります。まずはManacherのアルゴリズムを使わない愚直な方法についてみていきます。
Manacherのアルゴリズムを使わない場合
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
class Program { static void Main() { string str = Console.ReadLine(); // i番目を中心とする最長回文半径を求める for (int i = 0; i < str.Length; i++) { int k = 0; while (true) { // 中心からひとつずつ外側の文字が同じかどうか確認する // 比較対象となる文字が存在しないので終了 if (i - k < 0 || i + k == str.Length) break; // 文字が異なるので終了 if (str[i + k] != str[i - k]) break; k++; } Console.WriteLine(k); } } } |
こっちのほうがスマートでよさそう。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Program { static void Main() { string str = Console.ReadLine(); int[] p = new int[str.Length]; // i番目を中心とする最長回文半径を求める for (int i = 0; i < str.Length; i++) { while (i - p[i] >= 0 && i + p[i] < str.Length && str[i + p[i]] == str[i - p[i]]) p[i]++; } foreach(int i in p) Console.WriteLine(i); } } |
このアルゴリズムの時間計算量は O(文字列の長さ^2) となります。3000文字程度であればこれでも問題ありませんが、長い文字列になると時間がかかります。
ところで回文には前後を反転させても同じになる性質があります。では回文の最長回文半径がどうなっているでしょうか？たとえば回文 ‘aaabbbaaa’ の最長回文半径は〈1, 2, 1, 1, 5, 1, 1, 2, 1〉です。回文だと最長回文半径そのものも対称性を持っていることがわかります。この対称性を利用できないでしょうか？
Manacherのアルゴリズムで最長回文半径を求める
最長回文半径 p[i] を求める単純なアルゴリズムは、以下のようなものでした。
|
1 2 3 4 5 |
for (int i = 0; i < str.Length; i++) { while (i - p[i] >= 0 && i + p[i] < str.Length && str[i + p[i]] == str[i - p[i]]) p[i]++; } |
各最長回文半径を求める際に、今まで見た最長回文の右端の中で最も右にあるものをフロンティア、右端が最も右にある最長回文をフロンティアの最長回文と定義します。するとManacher のアルゴリズムは、
1. フロンティアの回文が i 番目の文字を覆っている場合はフロンティアの最長回文をもとに、回文の性質を使って暫定的な最長回文半径を求める
2. 今見ている最長回文の右端がフロンティアの位置に一致している場合のみ、最長回文半径を再計算してフロンティアを更新する
と表現することができます。このようなアルゴリズムで各文字を中心とする最長回文半径を求めることができるのです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
int[] p = new int[s.Length]; // ここに各最長回文半径が格納される int j = 0; // フロンティアの回文の中心の位置 for (int i = 0; i < s.Length; i++) { // フロンティアの回文が i 番目の文字を覆っていれば、 // フロンティアの最長回文をもとに、回文の性質を使って暫定的な最長回文半径を求める if (i < j + p[j]) p[i] = Math.Min(p[j - (i - j)], j + p[j] - i); if (j + p[j] <= i + p[i]) // 今見ている最長回文の右端がフロンティアの位置に一致している場合 { while (0 <= i - p[i] && i + p[i] < s.Length && s[i - p[i]] == s[i + p[i]]) // 最長回文半径を再計算 p[i]++; j = i; // フロンティアの回文の中心の位置を更新することでフロンティアを更新する } } |
偶数長の回文の最長回文半径
ここまでは奇数長の回文のみを考えてきました。しかし実際には偶数長の回文も存在します。では偶数長の回文の最長回文半径はどのようにして考えればよいでしょうか？
偶数長の回文とは文字と文字の間に中心がある回文です。そこで元の文字列の最初と最後および各文字間に適当な記号 ($ など) を挟んで奇数長の回文の最長回文半径を求める処理をおこないます。そして求められた回文半径を2で割る（端数切り捨て）と最長回文半径を求めることができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { // 適当な記号 ($ など) を挟んでManacher のアルゴリズムで最長回文半径を求める string str = Console.ReadLine(); char[] chars = str.ToArray(); string str2 = "$" + string.Join("$", chars) + "$"; int[] p = new int[str2.Length]; int j = 0; for (int i = 0; i < str2.Length; i++) { if (i < j + p[j]) p[i] = Math.Min(p[j - (i - j)], j + p[j] - i); if (j + p[j] <= i + p[i]) { while (0 <= i - p[i] && i + p[i] < str2.Length && str2[i - p[i]] == str2[i + p[i]]) p[i]++; j = i; } } // i番目の文字を中心とする回文半径 for (int i = 0; i < str.Length; i++) Console.WriteLine(p[i * 2 + 1] / 2); // i番目の文字とi+1番目の文字のあいだを中心とする回文半径 for (int i = 0; i < str.Length - 1; i++) Console.WriteLine(p[i * 2 + 2] / 2); } } |
文字列の各文字から始まる最長回文の長さを求める
各文字または各文字とその次の文字のあいだを中心とする最長回文半径から、回文の長さを求めることができます。また回文の長さを求めることができれば長さと最長回文半径の中心の文字の位置から回文の開始点を求めることができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
using System; using System.Collections.Generic; using System.Linq; public class Result { public Result(int start, int length) { Start = start; Length = length; } public int Length = 0; public int Start = 0; } class Program { static void Main() { string str = Console.ReadLine(); char[] chars = str.ToArray(); string str2 = "$" + string.Join("$", chars) + "$"; int[] p = new int[str2.Length]; { int j = 0; for (int i = 0; i < str2.Length; i++) { if (i < j + p[j]) p[i] = Math.Min(p[j - (i - j)], j + p[j] - i); if (j + p[j] <= i + p[i]) { while (0 <= i - p[i] && i + p[i] < str2.Length && str2[i - p[i]] == str2[i + p[i]]) p[i]++; j = i; } } } List<Result> results = new List<Result>(); for (int i = 0; i < str.Length; i++) { int radius = p[i * 2 + 1] / 2; int length = radius * 2 - 1; int start = i - radius + 1; results.Add(new Result(start, length)); } for (int i = 0; i < str.Length - 1; i++) { int radius = p[i * 2 + 1] / 2; int length = radius * 2; int start = i - radius + 1; results.Add(new Result(start, length)); } // ソートしたあとStartでグループ化 var groups = results.OrderBy(_ => _.Start).ThenByDescending(_ => _.Length).GroupBy(_=> _.Start); int preLength = 0; foreach (var group in groups) { // 開始点を1ずらすとすでに確定している最長回文よりも2短い長さかそれより長くなる。 // なので長いほうを採用する int length = Math.Max(group.First().Length, preLength - 2); Console.WriteLine(length); preLength = length; } } } |
