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)

Terjemahan bahasa Cina bagi

Brute force Approach

ialah:

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.

urutan dua panjang dan simpannya. Jadi dengan mengandaikan anda mencincang urutan yang dikira untuk mencapai sisipan dan carian O(1), ini menjadi O(n^2). Jumlah susulan juga adalah O(n^2), jadi ruang storan juga.

Ubah suai susulan sepunya terpanjang (LCS)

Algoritma #🎜🎜 #LCS mencari urutan sepunya terpanjang antara 2 rentetan. Ia adalah kaedah pengaturcaraan dinamik piawai yang menggunakan kaedah lelaran bagi matriks dua dimensi. Kerumitan masa ialah O(n^2). Kami hanya akan mencari rentetan yang diberikan itu sendiri dalam kaedah yang diubah suai. Namun begitu, kami juga akan menyemak sama ada indeks kedudukan semasa tidak sama.

Contoh

Lihat kod C++ di bawah untuk melaksanakan algoritma urutan lazim terpanjang yang diubah suai yang memudahkan kaedah kami mencari urutan berulang panjang 2 atau lebih -

#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;
}

Output

Repeated subsequence of length 2 or more: Yes

Sudah tentu, kerumitan masa dan ruang ialah O(n^2), tetapi daripada kaedah pertama, ia lebih elegan dan mudah untuk menghasilkan cincangan O(1).

Penyelesaian yang lebih baik

Dalam kaedah ini, kami akan cuba membuat beberapa pemerhatian berdasarkan kaedah sebelum ini.

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.

Contoh

Berdasarkan ketiga-tiga pemerhatian di atas, kami membuat kesimpulan bahawa jika kami mengalih keluar semua aksara yang muncul sekali dalam rentetan dan kemudian menyemak sama ada aksara tertentu muncul lebih daripada dua kali atau jika rentetan itu bukan palindrom, maka jawapan Kami adalah betul . Mari lihat penyelesaian yang lebih baik yang dilaksanakan dalam 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;
}

Output

Repeated subsequence of length 2 or more: Yes

KESIMPULAN

Kami membuat kesimpulan bahawa menggunakan pemerhatian dan cincang adalah cara terbaik untuk menyelesaikan masalah ini. Kerumitan masa ialah O(n). Kerumitan ruang juga mengikut urutan O(n), mencipta rentetan baharu dan cincangan 26 aksara yang berterusan.

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!