給定一個字串，找出一個長度至少為兩個、在字串中重複的子序列。子序列元素編號的索引不能處於相同的順序。
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 的索引）
這種方法將產生長度為 2（最小長度）的所有可能的子序列，並尋找我們是否已經看到該子序列與已找到的子序列。如果子序列已經存在，我們傳回 true 並終止程式；否則，在完成迭代後，如果我們什麼也沒找到，則傳回 false。
在最壞的情況下，這個子序列可能不存在，我們最終會產生所有可能的結果。
兩個長度的子序列並將它們儲存起來。因此，假設您對計算的子序列進行哈希處理以實現O(1)的插入和搜索，這將變為O(n^2)。總的子序列也是O(n^2)，所以儲存空間也是如此。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中文網其他相關文章！
