พิจารณาว่าเรามีพจนานุกรมและสตริง 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
