พิมพ์ subsequence ทั้งหมดของสตริงด้วย Iterative Method ใน C++

ในปัญหานี้ เราจะได้รับสตริง และต้องหา substring จากสตริงที่กำหนด Substring ที่ต้องการควรเริ่มต้นด้วย สระและจบด้วยตัวอักษรพยัญชนะ

String คือ อาเรย์ของตัวอักษร

Substring ที่จะสร้างในปัญหานี้ สามารถสร้างได้โดยการลบตัวอักษรบางส่วนของสตริง และไม่เปลี่ยนลำดับของสตริง

Input: 'abc'
Output: ab, ac, abc

เพื่อแก้ปัญหานี้ เราจะวนลูปผ่านสตริงและกำหนดสระและตรวจสอบลำดับถัดไป มาดูอัลกอริทึมเพื่อหาคำตอบ:

อัลกอริทึม

ขั้นตอนที่ 1: วนลูปแต่ละตัวอักษรของสตริงด้วยตัวแปร i
ขั้นตอนที่ 2: ถ้าตัวอักษรตัวที่ i เป็นสระ
ขั้นตอนที่ 3: ถ้าตัวอักษรตัวที่ j เป็นพยัญชนะ
ขั้นตอนที่ 4: เพิ่มลง HashSet substring จากตัวอักษรตัวแรกถึงตัวที่ j
ขั้นตอนที่ 5: ทำซ้ำขั้นตอนต่อไปเพื่อหา substrings จากสตริง

ใน iterative approach เราจะวนลูปผ่านสตริงทั้งหมด จาก 1 ถึง 2^{length(string)} - 1

โปรแกรมตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

string subString(string s, int binary) {
    string sub = "";
    int pos;
    while (binary > 0) {
        pos = log2(binary & -binary) + 1;
        sub = s[pos - 1] + sub;
        binary = (binary & ~(1 << (pos - 1)));
    }
    reverse(sub.begin(), sub.end());
    return sub;
}

void findAllSubStrings(string s) {
    map<int, set<string> > sorted_subsequence;
    int len = s.size();
    int limit = pow(2, len);
    for (int i = 1; i <= limit - 1; i++) {
        string sub = subString(s, i);
        sorted_subsequence[sub.length()].insert(sub);
    }
    for (auto it : sorted_subsequence) {
        for (auto ii : it.second)
            cout << ii << " ";
        cout << "\t";
    }
}

int main() {
    string s = "wxyz";
    cout << "The substring are :\n";
    findAllSubStrings(s);
    return 0;
}

ผลลัพธ์

The substring is -

w x y z wx wy wz xy xz yz wxy wxz wyz xyz wxyz