โปรแกรม C++ หาคำที่ยาวที่สุดในพจนานุกรมโดยการลบตัวอักษรจากสตริงที่กำหนด

พิจารณาว่าเรามีพจนานุกรม และสตริง s หาสตริงที่ยาวที่สุดในพจนานุกรม ที่สามารถสร้างได้โดยการลบตัวอักษรบางส่วนของสตริง s สมมติ s คือ "apbreoigroakml" พจนานุกรมมี {"prog", "ram", "program"} ผลลัพธ์จะเป็น "program"

เพื่อแก้ปัญหานี้ เราจะวนลูปทุกคำในพจนานุกรม และสำหรับแต่ละคำ เราจะตรวจสอบว่าคำนั้นเป็น subsequence ของสตริงที่กำหนดและยาวที่สุดของคำทั้งหมดที่เป็นเช่นนั้น สุดท้ายคืนค่าคำที่ยาวที่สุดซึ่งสตริงที่กำหนดเป็น subsequence

ตัวอย่าง

#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