Programme C++ pour déterminer si une chaîne donnée a une sous-séquence répétitive de longueur 2 ou plus

Étant donné une chaîne, trouvez une sous-séquence de longueur au moins deux qui est répétée dans la chaîne. Les indices des numéros d'éléments de sous-séquence ne peuvent pas être dans le même ordre.

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

Regardons quelques exemples ci-dessous pour comprendre comment cette approche fonctionne dans différentes situations -

Exemple 1 - str = "PNDPNSP"

Explication − Ici, la réponse est vraie car il y a une sous-séquence récurrente "PN" dans la chaîne.

Exemple 2 - str = "PPND"

Explication - Ici, la réponse est fausse car il n'y a pas de sous-séquence répétée de longueur au moins deux dans la chaîne.

Exemple 3 − str = "PPNP"

Explication - Ici, la réponse est correcte car les index "PP" 0 et 1 et les index "PP" 1 et 3 existent et les "PP" utilisés ont des index différents séquentiellement dans la sous-séquence. (indice basé sur 0)

Approche par force brute

Approche par force brute

Cette méthode générera toutes les sous-séquences possibles de longueur 2 (longueur minimale) et déterminera si nous avons déjà vu cette sous-séquence avec la sous-séquence trouvée. Si la sous-séquence existe déjà, nous renvoyons vrai et terminons le programme ; sinon, après avoir terminé l'itération, si nous ne trouvons rien, nous renvoyons faux.

Dans le pire des cas, cette sous-séquence peut ne pas exister et nous finissons par générer tous les résultats possibles.

Sous-séquence commune la plus longue modifiée (LCS)

L'algorithme LCS trouve la sous-séquence commune la plus longue dans 2 chaînes. Il s'agit d'une méthode de programmation dynamique standard qui utilise une méthode itérative de matrices bidimensionnelles. La complexité temporelle est O(n^2). Nous rechercherons uniquement la chaîne donnée elle-même dans la méthode modifiée. Néanmoins, nous vérifierons également si l'index de la position actuelle n'est pas le même.

Exemple

Consultez le code C++ ci-dessous pour implémenter l'algorithme de sous-séquence commune la plus longue modifiée qui aide notre méthode à trouver des sous-séquences répétitives de longueur 2 ou plus -

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

Sortie

Repeated subsequence of length 2 or more: Yes

Bien sûr, la complexité temporelle et spatiale est O(n^2), mais en regardant la première méthode, elle est plus élégante et produit facilement un hachage de O(1).

Solution améliorée

Dans cette méthode, nous essaierons de faire quelques observations basées sur la méthode précédente.

Observation 1 − Si un caractère apparaît plus de deux fois, la réponse est toujours vraie. Voyons pourquoi ?

Exemple - Dans la chaîne str = "AVHJFBABVNHFA" nous avons "AAA" aux positions 0, 6 et 12. donc On peut avoir "AA" aux index 0 et 6 comme sous-séquence, et "AA" aux index 6 et 12 comme sous-séquence comme un autre.

Observation 2 - Si un caractère n'est répété qu'une seule fois, il ne peut pas contribuer à nos résultats sous-séquence, car il ne sera disponible que dans au plus une sous-séquence. ça ne marchera pas Parce que nous avons besoin d'au moins deux sous-séquences. Nous pouvons donc supprimer ou ignorer tous les caractères arrivé en même temps.

Observation 3 − Si une chaîne est un palindrome et que les deux premières observations s'appliquent, alors la réponse est Toujours faux sauf si la longueur de la chaîne est impaire. Voyons pourquoi ?

Exemple - String str = "PNDDNP"

Explication - Maintenant, les personnages ne sont pas dans l'ordre donc on ne les retrouve jamais Les sous-séquences ont le même ordre, ce n’est donc pas possible.

Exemple

Sur la base des trois observations ci-dessus, nous concluons que si nous supprimons tous les caractères qui apparaissent une fois dans la chaîne et vérifions ensuite si un certain caractère apparaît plus de deux fois ou si la chaîne n'est pas un palindrome, alors notre réponse est correcte. Voyons la solution améliorée implémentée en 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;
}

Sortie

Repeated subsequence of length 2 or more: Yes

Conclusion

Nous avons conclu que l'utilisation d'observations et de hachages est le meilleur moyen de résoudre ce problème. La complexité temporelle est O(n). La complexité spatiale est également de l'ordre de O(n), créant une nouvelle chaîne et un hachage constant de 26 caractères.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!