C++で文字列から一部の文字を削除して辞書内の最長の単語を見つける方法

問題の概要

辞書と文字列 s が与えられたとします。このとき、文字列 s から一部の文字を削除(つまり残りの文字の順序を保ったまま)することで作成できる、辞書内の最長の単語を見つけるのが目的です。

例えば、文字列 s が "apbreoigroakml" で、辞書が {"prog", "ram", "program"} の場合、答えは "program" になります。これは "program" の各文字が s に順番どおりに現れている(部分列となっている)ためです。

解決のアプローチ

この問題を解くには、次の手順で進めます。

まず、辞書内のすべての単語を走査します。次に、各単語について「その単語が与えられた文字列 s の部分列であるか」を判定します。部分列である単語の中で最も長いものを結果として返せばよいのです。

部分列の判定方法

部分列の判定は、2つのインデックスを使った貪欲法で効率的に行えます。文字列 s を先頭から順に走査しながら、判定対象の単語の文字と一致するたびに単語側のインデックスを進めます。最終的に単語のすべての文字が一致していれば、その単語は s の部分列であると判断できます。

アルゴリズムの手順

1. 結果を格納する文字列を空文字列で初期化します。

2. 辞書内の各単語について、現在の結果より長い場合にのみ部分列判定を行います(不要な計算を省くため)。

3. 単語が s の部分列であれば、結果とその長さを更新します。

4. すべての単語を確認した後、結果を返します。

C++での実装例

#include<iostream>
#include<vector>
using namespace std;
bool isSubSequence(string s1, string s2) {
    int m = s1.length(), n = s2.length();
    int j = 0;
    for (int i=0; i<n&&j<m; i++)
    if (s1[j] == s2[i])
        j++;
    return (j==m);
}
string getLongestSubstr(vector <string > dict, string s) {
    string result = "";
    int length = 0;
    for (string word : dict) {
        if (length < word.length() && isSubSequence(word, s)) {
            result = word;
            length = word.length();
        }
    }
    return result;
}
int main() {
    vector <string > dict = {"prog", "ram", "program"};
    string str = "apbreoigroakml" ;
    cout << getLongestSubstr(dict, str) << endl;
}

出力

program

計算量について

辞書内の単語数を D、文字列 s の長さを N とすると、各単語の部分列判定は O(N) で行えるため、全体の時間計算量は O(D × N) となります。空間計算量は O(1) で、追加のメモリはほとんど必要ありません。