Cho chuỗi, tìm dãy con bắt đầu bằng nguyên âm, kết thúc bằng phụ âm.
Input: 'abc' Output: ab, ac, abc
Giải pháp: Duyệt chuỗi, cố định nguyên âm tại i, duyệt j từ cuối về, nếu j là phụ âm thì lấy dãy con i..j và đệ quy xóa ký tự giữa.
Chương trình minh họa
#include <bits/stdc++.h>
using namespace std;
set<string> st;
bool isaVowel(char c);
bool isaConsonant(char c);
void findSubSequence(string str);
int main(){
string s = "abekns";
findSubSequence(s);
cout << "Các dãy con tạo được :\n";
for (auto i : st) cout << i << " ";
cout << endl;
return 0;
}
bool isaVowel(char c) {
return (c=='a'||c=='e'||c=='i'||c=='o'||c=='u');
}
bool isaConsonant(char c) {
return !isaVowel(c);
}
void findSubSequence(string str) {
for (int i = 0; i < str.length(); i++) {
if (isaVowel(str[i])) {
for (int j = str.length() - 1; j >= i; j--) {
if (isaConsonant(str[j])) {
string str_sub = str.substr(i, j + 1);
st.insert(str_sub);
for (int k = 1; k < str_sub.length() - 1; k++){
string sb = str_sub;
sb.erase(sb.begin() + k);
findSubSequence(sb);
}
}
}
}
}
}
Kết quả
ab abek abekn abekns abeks aben abens abes abk abkn abkns abks abn abns abs aek aekn aekns aeks aen aens aes ak akn akns aks an ans as ek ekn ekns eks en ens es