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個字元的雜湊表。

更新於：2022年8月10日

206 次瀏覽

開啟您的職業生涯

透過完成課程獲得認證

開始學習
廣告