c++ 求字符串的子序列的反集。
时间: 2023-08-10 10:06:10 浏览: 56
字符串的子序列的反集就是字符串中不是任何子序列的字符构成的字符串。可以先求出字符串的所有子序列,然后再遍历整个字符串,将不在子序列中的字符添加到反集中即可。
以下是 C++ 的实现代码:
```c++
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<string> getSubsequence(string s) {
vector<string> ans{""};
for (char c : s) {
int n = ans.size();
for (int i = 0; i < n; ++i) {
ans.push_back(ans[i] + c);
}
}
return ans;
}
string reverseSubsequence(string s) {
vector<string> subs = getSubsequence(s);
vector<bool> is_sub(s.size()+1, false);
for (string sub : subs) {
for (int i = 0, j = 0; i < s.size(); ++i) {
if (j < sub.size() && s[i] == sub[j]) {
++j;
} else {
is_sub[i+1] = true;
}
}
}
string ans;
for (int i = 0; i < s.size(); ++i) {
if (!is_sub[i+1]) {
ans += s[i];
}
}
return ans;
}
int main() {
string s;
cin >> s;
string ans = reverseSubsequence(s);
cout << ans << endl;
return 0;
}
```
首先定义一个函数 `getSubsequence` 来获取字符串的所有子序列。该函数通过遍历字符串中的每个字符,将当前字符插入到已有子序列的末尾,从而得到新的子序列。最终得到的所有子序列存储在一个 `vector` 容器中。
接下来,遍历所有子序列,将每个子序列的所有字符在原字符串中对应的位置标记为已出现过。然后遍历整个字符串,将没有被标记的字符添加到反集中。
由于字符串的子序列个数是指数级别的,因此该算法的时间复杂度为 $O(2^n \cdot n)$。在字符串较长时可能会超时,可以考虑采用其他更优秀的算法来解决。