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