C++で最短の回文を求める方法｜KMP法のLPS配列を活用した実装例

問題概要

文字列 s が与えられます。この文字列の先頭に文字を追加していくことで、回文（前から読んでも後ろから読んでも同じになる文字列）に変換することができます。ここでの課題は、その操作によって作れる最短の回文を見つけることです。

たとえば、文字列が「abcc」の場合、答えは「ccbabcc」となります。

解き方のアプローチ

この問題は、KMP法（文字列検索アルゴリズム）で使われる LPS配列（接尾辞とも一致する最長の接頭辞の長さを格納する配列）を応用すると、O(n) の計算量で効率よく解くことができます。

ポイントは次のとおりです。

• 元の文字列 s と、それを反転させた文字列を、区切り文字「#」を挟んで連結します。この「#」は、両者が混ざって誤マッチするのを防ぐためのダミー文字です（入力に含まれない任意の文字で構いません）。
• 連結した文字列に対してLPS配列を構築すると、その最終要素の値が「元の文字列の先頭から始まる最長の回文の長さ」を表します。
• したがって、回文になっていない残りの部分（s の末尾側）を取り出して反転し、先頭に付け足せば、それが最短の回文になります。

手順

• n := s のサイズ、s1 := s、s2 := s
• 文字列 s2 を反転する
• s2 := s + "#" + s2 を連結する
• s2 と同じサイズの配列 lps を定義する
• j := 0、i := 1
• i < s2 のサイズである間、以下を繰り返す
  • s2[i] が s2[j] と等しい場合
    • lps[i] := j + 1
    • i と j をそれぞれ 1 増やす
  • それ以外の場合
    • j > 0 ならば、j := lps[j - 1]
    • そうでなければ、i を 1 増やす
• extra := s.substr(lps[lps.size() - 1], n - lps[lps.size() - 1])（回文になっていない末尾部分）
• extra を反転する
• extra + s を返す

C++ 実装例

以下の実装を見ると、処理の流れがより明確になります。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    string shortestPalindrome(string s) {
        int n = s.size();
        string s1 = s;
        string s2 = s;
        reverse(s2.begin(), s2.end());
        s2 = s + "#" + s2;
        vector <int> lps(s2.size());
        int j = 0;
        int i = 1;
        while(i < s2.size()){
            if(s2[i] == s2[j]){
                lps[i] = j + 1;
                j++;
                i++;
            } else {
                if(j > 0){
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        string extra = s.substr(lps[lps.size() - 1], n - lps[lps.size() - 1]);
        reverse(extra.begin(), extra.end());
        return extra + s;
    }
};
main(){
    Solution ob;
    cout << (ob.shortestPalindrome("abcc"));
}

入力

"abcc"

出力

ccbabcc

計算量について

LPS配列の構築は線形時間 O(n) で完了し、必要な追加メモリも O(n) にとどまります。一方、「先頭に1文字ずつ追加しては回文判定をする」という素朴なアプローチでは、最悪の場合 O(n²) の時間がかかる可能性があります。そのため、本手法は特に長い文字列を扱う際に大きな優位性を発揮します。