C++程序用于查找给定字符串是否有长度为2或更长的重复子序列

给定一个字符串，找到一个长度至少为两个、在字符串中重复的子序列。子序列元素编号的索引不能处于相同的顺序。

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。

Mulan AI

画布式AI视频创作平台，轻松制作爆款视频

下载

在最坏的情况下，这个子序列可能不存在，我们最终会生成所有可能的结果。

修改后的最长公共子序列（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<=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)，但是从第一种方法来看，它更加优雅且容易产生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 < 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个字符的哈希。