数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++程序：判断给定字符串是否存在长度大于等于2的重复子序列
给定一个字符串，找到一个长度至少为2的子序列，该子序列在字符串中重复出现。子序列元素的索引号不必按相同顺序排列。
string s = "PNDPNSP";
print("Repeated subsequence of length 2 or more: ", (check(s) ? "Yes" : "No"));
让我们看下面几个例子，看看该方法在不同情况下的工作方式：
示例1 − str = "PNDPNSP"
说明 − 答案为真，因为字符串中重复出现了子序列"PN"。
示例2 − str = "PPND"
说明 − 答案为假，因为字符串中不存在长度至少为2的重复子序列。
示例3 − str = "PPNP"
说明 − 答案为真，因为存在"PP"（索引0和1）和"PP"（索引1和3），并且使用的"PP"在子序列中的索引顺序不同。（基于0的索引）
暴力搜索方法
这种方法将生成所有长度为2（最小长度）的可能的子序列，并查找是否已经找到该子序列。如果子序列已经存在，则返回true并终止程序；否则，在完整迭代后，如果什么也没找到，则返回false。
在最坏情况下，子序列不存在，我们将最终生成所有可能的长度为2的子序列并存储它们。因此，这变成了O(n^2)，假设你对计算出的子序列进行哈希处理，以便O(1)插入和搜索。子序列总数也是O(n^2)，因此是存储空间。
改进的最长公共子序列(LCS)算法
LCS算法查找两个字符串中最长的公共子序列。这是一种标准的动态规划方法，采用带有二维矩阵的迭代方法。时间复杂度为O(n^2)。在我们的改进方法中，我们将只搜索给定字符串本身。但是，我们还将检查当前位置的索引是否相同。
示例
请看下面的C++代码，它实现了改进的最长公共子序列算法，该算法帮助我们的方法找到长度为2或更长的重复子序列：
#include <iostream> using namespace std; bool modifiedLongestCommonSubsequence(string s) { int n = s.length(); int dp[n+1][n+1]; for (int i=0; i<=n; i++) fill(dp[i], dp[i]+n+1, 0); for (int i=1; i<=n; i++) { for (int j=1; j<=n; j++) { if (s[i-1]==s[j-1] && i!=j) { dp[i][j] = 1 + dp[i-1][j-1]; } else { dp[i][j] = max(dp[i][j-1], dp[i-1][j]); } } } if(dp[n][n] > 1) return true; return false; } int main() { string str = "PNDPNSP"; cout << "Repeated subsequence of length 2 or more: " << (modifiedLongestCommonSubsequence(str) ? "Yes" : "No"); return 0; }
输出
Repeated subsequence of length 2 or more: Yes
当然，时间和空间复杂度是O(n^2)，但它比方法1更优雅，并且更容易进行O(1)哈希。
改进的解决方案
在这种方法中，我们将尝试改进我们之前的方法并进行一些观察。
观察1 − 如果一个字符出现两次以上，答案总是为真。让我们看看为什么？
示例 − 在字符串str = "AVHJFBABVNHFA"中，我们在位置0、6和12处有"AAA"。因此，我们可以从索引0和6取"AA"作为第一个子序列，从索引6和12取"AA"作为另一个子序列。
观察2 − 如果一个字符只重复一次，它就不能对我们的子序列做出贡献，因为它最多只能在一个子序列中出现。它不起作用，因为我们需要至少两个子序列。因此，我们可以删除或忽略所有只出现一次的字符。
观察3 − 如果一个字符串是回文，并且前两个观察结果适用，则答案总是为假，除非字符串的长度为奇数。让我们看看为什么？
示例 − 字符串str = "PNDDNP"
说明 − 现在，字符的顺序不同，因此我们将永远无法找到具有相同顺序的子序列，因此这是不可能的。
示例
根据以上三个观察结果，我们得出结论：如果我们删除字符串中所有只出现一次的字符，然后检查某个字符是否出现超过两次，或者字符串不是回文，那么我们的答案就是真。让我们看看C++中改进解决方案的实现：
#include <iostream> using namespace std; bool isPalindrome(string s) { for(int i=0;i<s.size()/2;i++) { if(s[i]!=s[s.size()-1-i]) { return false; } } return true; } bool check(string s) { int hash[26] = {0}; for (int i = 0; i < s.size(); i++) { hash[s[i]-'a']++; if (hash[s[i]-'a'] > 2) { return true; } } int k = 0; string mstr = ""; for (int i = 0; i < s.size(); i++) { if (hash[s[i]-'a'] > 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: " << (check(s) ? "Yes" : "No"); return 0; }
输出
Repeated subsequence of length 2 or more: Yes
结论
我们得出结论，这个问题最好通过观察和哈希来解决。时间复杂度为O(n)。空间复杂度也是O(n)，创建了一个新的字符串和一个常量26个字符的哈希表。
206 次浏览
