C++で文字列の最長ハッピープレフィックスを求める方法

問題の概要

文字列 s が与えられたとき、その最長ハッピープレフィックス（happy prefix）を求める問題です。ハッピープレフィックスとは、「文字列自身を除いた空でない接頭辞であり、かつ同時に接尾辞でもある文字列」のことです。該当するものが存在しない場合は、単に空文字列を返します。

たとえば入力が "madam" の場合、出力は "m" になります。"madam" 自身を除くと、接頭辞は "m"、"ma"、"mad"、"mada" の4つ、接尾辞も "m"、"am"、"dam"、"adam" の4つ存在します。このうち「接頭辞でもあり接尾辞でもある」最長の文字列が "m" というわけです。

解決アプローチ：KMPアルゴリズムのLPS配列

この問題は、KMP文字列検索アルゴリズムで使われる LPS配列（Longest Proper Prefix which is also Suffix）を利用すると効率的に解けます。LPS配列の各要素 ret[i] には、「位置 i で終わる部分文字列における、接頭辞かつ接尾辞となる最長の長さ」が格納されます。したがって、文字列全体に対する答えは、配列の最後の要素 v[n-1] を参照するだけで求められます。

アルゴリズムの手順

関数 lps() の処理：

• 関数 lps() を定義し、文字列 s を受け取る
• n := 文字列 s の長さ
• サイズ n の配列 ret を定義する
• j := 0、i := 1 と初期化する
• i < n の間、以下を繰り返す：
  
  • s[i] と s[j] が一致する場合：
    
    • ret[i] := j + 1
    • i を1増やす
    • j を1増やす
  • 一致しない場合：
    
    • j > 0 ならば j := ret[j - 1]
    • それ以外の場合は i を1増やす
• ret を返す

メイン処理：

• n := 文字列 s の長さ
• n が 1 の場合、空文字列を返す
• 配列 v = lps(s) を取得する
• x := v[n - 1]
• ret := 空文字列
• i = 0 から x 未満まで繰り返し、ret := ret + s[i] を行う
• ret を返す

C++による実装例

理解を深めるために、以下の実装例をご覧ください。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    vector <int> lps(string s){
       int n = s.size();
       vector<int> ret(n);
       int j = 0;
       int i = 1;
       while (i < n) {
          if (s[i] == s[j]) {
             ret[i] = j + 1;
             i++;
             j++;
          }
          else if (s[i] != s[j]) {
             if (j > 0)
                j = ret[j - 1];
             else {
                i++;
             }
          }
       }
       return ret;
    }
    string longestPrefix(string s) {
       int n = s.size();
       if (n == 1)
       return "";
       vector<int> v = lps(s);
       int x = v[n - 1];
       string ret = "";
       for (int i = 0; i < x; i++) {
          ret += s[i];
       }
       return ret;
    }
};
main(){
    Solution ob;
    cout << (ob.longestPrefix("madam"));
}

入力

"madam"

出力

m

計算量について

このアルゴリズムの時間計算量は O(n)、空間計算量も O(n) です。LPS配列の構築では、ポインタ i と j がそれぞれ文字列長を超えて後退することがないため、線形時間で処理が完了します。一方、すべての接頭辞と接尾辞を総当たりで比較するナイーブな手法では最悪 O(n²) の計算量が必要になるため、KMPのLPS配列を活用するこのアプローチが非常に効率的です。