C++で接尾辞と一致する最長の接頭辞を見つけるプログラム

問題概要

文字列 s が与えられたとき、s 自身を除いた上で、同時に接尾辞（サフィックス）にもなる最長の接頭辞（プレフィックス）を見つけることを考えます。該当する接頭辞が存在しない場合は、空文字列を返します。

具体例

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

解法のアプローチ

この問題は、KMP文字列検索アルゴリズムで使われる LPS配列を利用すると効率的に解けます。LPS配列の各要素には、「その位置までの部分文字列において、適切な接頭辞かつ接尾辞となる最長の長さ」が格納されます。したがって、文字列全体に対する答えは配列の最後の要素を参照するだけで求まり、計算量は O(n) と線形時間で済むのが大きな利点です。

LPS関数の構築手順

• 関数 lps(s) を定義します。
• n := 文字列 s の長さとします。
• サイズ n の配列 ret を定義します。
• j := 0、i := 1 で初期化します。
• i < n の間、次を繰り返します。
  • s[i] == s[j] の場合：ret[i] := j + 1 とし、i と j をそれぞれ1増やします。
  • s[i] != s[j] の場合：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("helloworldhello"));
}

入力

"helloworldhello"

出力

hello

この例では、「helloworldhello」の先頭と末尾に共通して現れる最長の部分文字列「hello」が出力されます。LPS配列を一度構築するだけで答えが得られるため、非常にシンプルかつ高速な解法といえます。