C++程式用於尋找給定字串是否有長度為2或更長的重複子序列

給定一個字串，找出一個長度至少為兩個、在字串中重複的子序列。子序列元素編號的索引不能處於相同的順序。

string s = "PNDPNSP";
print("Repeated subsequence of length 2 or more: ", (check(s) ? "Yes" : "No"));

讓我們來看看下面的幾個例子，以了解這種方法在不同情況下的工作原理 -

範例 1 - str = "PNDPNSP"

#Explanation − 這裡，答案是true，因為字串中有一個重複出現的子序列"PN"。

範例 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 <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)，但是從第一種方法來看，它更加優雅且容易產生O(1)的哈希。

改進的解決方案

在這個方法中，我們將嘗試在先前的方法基礎上進行一些觀察。

觀察1 − 如果一個字元出現超過兩次，答案總是真的。讓我們看看為什麼？

範例 - 在字串 str = "AVHJFBABVNHFA" 中，我們在位置 0、6 和 12 中有 "AAA"。所以 我們可以將索引為0和6的"AA"作為一個子序列，以及將索引為6和12的"AA"作為一個子序列 作為另一個。

觀察 2 - 如果一個字元只重複一次，它不能對我們的結果做出貢獻 子序列，因為它只會在最多一個子序列中可用。它將無法運作 因為我們需要至少兩個子序列。所以我們可以刪除或忽略所有字符 發生在同一時間。

觀察3 − 如果一個字串是回文，並且前兩個觀察都適用，那麼答案是 除非字串長度為奇數，否則始終為 false。讓我們看看為什麼？

範例 - 字串 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個字元的雜湊。

以上是C++程式用於尋找給定字串是否有長度為2或更長的重複子序列的詳細內容。更多資訊請關注PHP中文網其他相關文章！