Program C++ untuk mencari sama ada rentetan yang diberikan mempunyai urutan berulang dengan panjang 2 atau lebih

Diberi rentetan, cari urutan panjang sekurang-kurangnya dua yang diulang dalam rentetan. Indeks nombor unsur berikutnya tidak boleh dalam susunan yang sama.

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

Mari lihat beberapa contoh di bawah untuk memahami cara pendekatan ini berfungsi dalam situasi yang berbeza -

Contoh 1 - str = "PNDPNSP"

Penjelasan − Di sini, jawapannya adalah benar kerana terdapat urutan berulang "PN" dalam rentetan.

Contoh 2 - str = "PPND"

Penjelasan - Di sini, jawapannya salah kerana tidak ada urutan panjang yang berulang sekurang-kurangnya dua dalam rentetan.

Contoh 3 − str = "PPNP"

Penjelasan - Di sini, jawapannya betul kerana "PP" indeks 0 dan 1 dan "PP" indeks 1 dan 3 wujud dan "PP" yang digunakan adalah dalam urutan mengikut Urutan mempunyai indeks yang berbeza. (indeks berasaskan 0)

Brute force Approach

brute force approach

Kaedah ini akan menjana semua kemungkinan urutan panjang 2 (panjang minimum) dan mencari jika kita telah melihat urutan ini dengan urutan yang ditemui. Jika susulan sudah wujud, kami mengembalikan benar dan menamatkan program jika tidak, selepas melengkapkan lelaran, jika kami tidak menemui apa-apa, kami mengembalikan palsu.

Dalam kes yang paling teruk, urutan ini mungkin tidak wujud dan kami akhirnya menjana semua hasil yang mungkin.

Ubah suai susulan sepunya terpanjang (LCS)

#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

Salin selepas log masuk

Salin selepas log masuk

Pemerhatian 1 − Jika watak muncul lebih daripada dua kali, jawapannya sentiasa benar. Jom tengok kenapa?

Contoh - Dalam rentetan str = "AVHJFBABVNHFA" kita mempunyai "AAA" dalam kedudukan 0, 6 dan 12. jadi Kita boleh mempunyai "AA" pada indeks 0 dan 6 sebagai susulan, dan "AA" pada indeks 6 dan 12 sebagai susulan sebagai yang lain.

Pemerhatian 2 - Jika aksara diulang sekali sahaja, ia tidak boleh menyumbang kepada keputusan kami berikutnya, kerana ia hanya akan tersedia dalam paling banyak satu urutan. ia tidak akan berfungsi Kerana kita memerlukan sekurang-kurangnya dua urutan. Jadi kita boleh mengalih keluar atau mengabaikan semua aksara berlaku pada masa yang sama.

Pemerhatian 3 − Jika rentetan ialah palindrom, dan dua pemerhatian pertama terpakai, maka jawapannya ialah Sentiasa palsu melainkan panjang rentetannya ganjil. Jom tengok kenapa?

Contoh - String str = "PNDDNP"

Penjelasan - Sekarang, watak-wataknya tidak teratur jadi kami tidak dapat mencari Susunan mempunyai susunan yang sama, jadi ini tidak mungkin.

#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

Salin selepas log masuk

Salin selepas log masuk

KESIMPULAN

Atas ialah kandungan terperinci Program C++ untuk mencari sama ada rentetan yang diberikan mempunyai urutan berulang dengan panjang 2 atau lebih. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!