给定一个字符串，找到一个长度至少为两个、在字符串中重复的子序列。子序列元素编号的索引不能处于相同的顺序。
string s = "PNDPNSP";print("Repeated subsequence of length 2 or more: ", (check(s) ? "Yes" : "No"));
登录后复制
让我们看一下下面的几个例子，以了解这种方法在不同情况下的工作原理 –
示例 1 – str = “PNDPNSP”
Explanation − 这里，答案是true，因为字符串中有一个重复出现的子序列”PN”。
立即学习“C++免费学习笔记（深入）”；
示例 2 – str = “PPND”
解释 – 这里，答案是错误的，因为字符串中没有重复的长度至少为两个的子序列。
示例3 − str = “PPNP”
解释 – 这里，答案是正确的，因为“PP”索引0和1以及“PP”索引1和3存在，并且使用的“PP”在子序列中按顺序具有不同的索引。 （基于 0 的索引）
Brute force Approach
的中文翻译为：
暴力破解方法
这种方法将生成长度为 2（最小长度）的所有可能的子序列，并查找我们是否已经看到该子序列与已找到的子序列。如果子序列已经存在，我们返回 true 并终止程序；否则，在完成迭代后，如果我们什么也没找到，则返回 false。
在最坏的情况下，这个子序列可能不存在，我们最终会生成所有可能的结果。
两个长度的子序列并将它们存储起来。因此，假设您对计算的子序列进行哈希处理以实现O(1)的插入和搜索，这将变为O(n^2)。总的子序列也是O(n^2)，所以存储空间也是如此。
修改后的最长公共子序列（LCS）
LCS 算法找到 2 个字符串中的最长公共子序列。它是一种标准的动态规划方法，使用二维矩阵的迭代方法。时间复杂度为O(n^2)。我们将仅在修改后的方法中搜索给定字符串本身。尽管如此，我们还将检查当前位置的索引是否不相同。
示例
查看下面的 C++ 代码来实现修改后的最长公共子序列算法，该算法有助于我们的方法找到长度为 2 或以上的重复子序列 –
#include using namespace std;bool modifiedLongestCommonSubsequence(string s) { int n = s.length(); int dp[n+1][n+1]; for (int i=0; i 1) return true; return false;}int main() { string str = "PNDPNSP"; cout 输出
Repeated subsequence of length 2 or more: Yes
登录后复制
当然，时间和空间复杂度是O(n^2)，但是从第一种方法来看，它更加优雅且容易产生O(1)的哈希。
改进的解决方案
在这种方法中，我们将尝试在之前的方法基础上进行一些观察。
观察1 − 如果一个字符出现超过两次，答案总是真的。让我们看看为什么？
示例 - 在字符串 str = "AVHJFBABVNHFA" 中，我们在位置 0、6 和 12 中有 "AAA"。所以我们可以将索引为0和6的"AA"作为一个子序列，以及将索引为6和12的"AA"作为一个子序列作为另一个。
观察 2 - 如果一个字符只重复一次，它不能对我们的结果做出贡献子序列，因为它只会在最多一个子序列中可用。它将无法工作因为我们需要至少两个子序列。所以我们可以删除或忽略所有字符发生在同一时间。
观察3 − 如果一个字符串是回文，并且前两个观察都适用，那么答案是除非字符串长度为奇数，否则始终为 false。让我们看看为什么？
示例 - 字符串 str = "PNDDNP"
解释 - 现在，字符不按顺序排列，因此我们永远无法找到子序列具有相同的顺序，因此不可能。
示例
根据上述所有三个观察结果，我们得出的结论是，如果我们删除字符串中出现一次的所有字符，然后检查某个字符是否出现两次以上或者字符串是否不是回文，那么我们的答案是正确的。让我们看看改进后的解决方案在 C++ 中的实现 -
#include using namespace std;bool isPalindrome(string s) { for(int i=0;i 2) { return true; } } int k = 0; string mstr = ""; for (int i = 0; i 1) { mstr[k++] = s[i]; } } if (isPalindrome(mstr)) { return false; } return true;}int main() { string s = "PNDPNSP"; cout 输出
Repeated subsequence of length 2 or more: Yes
登录后复制
结论
我们得出结论，使用观察和哈希是解决这个问题的最佳方法。时间复杂度为O(n)。空间复杂度也是O(n)的顺序，创建一个新的字符串和常数26个字符的哈希。
以上就是C++程序用于查找给定字符串是否有长度为2或更长的重复子序列的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2581228.html
