La sous-chaîne la plus longue dans laquelle les caractères adjacents n'ont pas de lettres anglaises adjacentes

Dans le domaine de la manipulation de chaînes, l'identification de modèles et l'extraction de sous-chaînes significatives sont des tâches courantes. Un problème intéressant consiste à trouver la sous-chaîne la plus longue dans laquelle aucun caractère adjacent n'est adjacent à une lettre anglaise. Dans cet article, nous examinerons une solution efficace à ce problème en utilisant C++ et fournirons des explications claires et des exemples de cas de test.

Énoncé du problème

Étant donné une chaîne de lettres anglaises minuscules, nous devons trouver la longueur de la sous-chaîne la plus longue dans laquelle aucun caractère adjacent n'est des lettres anglaises adjacentes. Par exemple, dans la chaîne "abacabx", la sous-chaîne la plus longue qui remplit cette condition est "abx", avec une longueur de 3.

Méthodes et algorithmes

Pour résoudre ce problème, nous pouvons utiliser la méthode gourmande. Nous allons parcourir la chaîne donnée et vérifier si le caractère actuel et le caractère précédent sont des lettres anglaises adjacentes. Si c'est le cas, nous commençons une nouvelle sous-chaîne. Sinon, nous développons la sous-chaîne existante. En mettant à jour la sous-chaîne la plus longue chaque fois que sa longueur dépasse le maximum précédent, nous pouvons trouver le résultat souhaité.

Implémentation C++

C'est le code C++ qui résout le problème &moins,

#include <iostream>
#include <string>
using namespace std;

int findLongestSubstring(const string& str) {
   int maxLength = 0;
   int currentLength = 1;
   
   for (int i = 1; i < str.length(); i++) {
      if (abs(str[i] - str[i - 1]) != 1) {
         currentLength++;
      } else {
         maxLength = max(maxLength, currentLength);
         currentLength = 1;
      }
   }
   
   maxLength = max(maxLength, currentLength);
    return maxLength;
}

int main() {
   string inputString = "abacabx";
   int longestSubstringLength = findLongestSubstring(inputString);
   
   cout << "Longest substring length: " << longestSubstringLength << endl;
   
   return 0;
}

Sortie

Longest substring length: 3

Explication du code

La fonction findLongestSubstring accepte une chaîne d'entrée comme paramètre et renvoie la longueur de la plus longue sous-chaîne de caractères alphabétiques anglais non adjacents.

Nous initialisons maxLength et currentLength à 0 et 1 respectivement. Ensuite, nous parcourons la chaîne en commençant par le deuxième caractère. Si la différence absolue entre le caractère actuel et le caractère précédent n’est pas égale à 1, currentLength est augmenté pour étendre la sous-chaîne actuelle. Sinon, si la longueur actuelle dépasse le maximum précédent, nous mettons à jour maxLength et réinitialisons currentLength à 1.

Enfin, nous renvoyons la longueur maximale trouvée. Dans la fonction principale, nous fournissons un exemple de chaîne d'entrée "abacabx" et imprimons la longueur de la sous-chaîne la plus longue.

Exemples de cas de test

Considérons l'exemple de chaîne "abacabx" pour démontrer notre solution.

Entrez

string inputString = "abacabx";

Dans cet exemple, la sous-chaîne la plus longue sans caractères alphabétiques anglais adjacents est "abx", d'une longueur de 3.

Conclusion

En adoptant une méthode simple et efficace, nous avons résolu avec succès le problème de trouver la plus longue sous-chaîne de lettres anglaises non adjacentes en utilisant C++. Comprendre le code et les explications fournies vous permettra de résoudre des problèmes similaires impliquant la manipulation de chaînes.

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!