Cho chuỗi, tìm các dãy con bắt đầu bằng nguyên âm và kết thúc bằng phụ âm.
Dãy con được tạo bằng cách xóa một số ký tự, không thay đổi thứ tự.
Input: 'abc' Output: ab, ac, abc
Giải pháp: Duyệt chuỗi, cố định nguyên âm, kiểm tra ký tự tiếp theo.
Thuật toán
Bước 1: Duyệt từng ký tự i. Bước 2: Nếu i là nguyên âm. Bước 3: Nếu j là phụ âm. Bước 4: Thêm dãy con từ i đến j vào HashSet. Bước 5: Lặp lại.
Cách lặp: Duyệt từ 1 đến 2^len - 1, dùng bitmask để tạo dãy con.
Chương trình minh họa
#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 << "Các dãy con là :\n";
findAllSubStrings(s);
return 0;
}
Kết quả
Các dãy con là:
w x y z wx wy wz xy xz yz wxy wxz wyz xyz wxyz