C ++で指定された文字列の一部の文字を削除して、辞書で最大の単語を検索します

辞書と文字列sがあるとします。辞書で最も長い文字列を見つけます。これは、文字列sの一部の文字を削除することで形成できます。 sが「apbreoigroakml」であると仮定します。辞書には{「prog」、「ram」、「program」}があり、結果は「program」になります。

これを解決するために、すべての辞書の単語をトラバースし、各単語について、指定された文字列のサブシーケンスがそのようなすべての単語の中で最も長いかどうかを確認します。最後に、指定された文字列をサブシーケンスとして含む最長の単語を返します。

例

#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