Vérifie si la sous-chaîne S1 apparaît après toute occurrence de la sous-chaîne S2 dans la phrase donnée

Dans ce problème, nous devons vérifier si la sous-chaîne S1 apparaît après toute occurrence de la sous-chaîne S2 dans une chaîne S donnée. Nous pouvons résoudre ce problème en comparant les index de départ de S1 et S2 dans la chaîne S. p>

Énoncé du problème - On nous donne trois sous-chaînes nommées S, S1 et S2. La chaîne S contient toujours S1 comme sous-chaîne. Nous devons vérifier si la sous-chaîne S1 apparaît après la sous-chaîne S2 dans une chaîne S donnée.

Exemple

Entrez – S = "abxtutorialspointwelcomepoint", S1 = "Bienvenue", S2 = "point"

Sortie – Oui

Explication – Dans la chaîne S, la sous-chaîne « point » apparaît 2 fois. L'un avant "bienvenue" et l'autre après "bienvenue". Ainsi, nous pouvons dire que la chaîne S1 apparaît après toute occurrence de la chaîne S2

Entrée– S = "abcdefgh", S1 = "abcd", S2 = "gh";

Sortie – Non

ExplicationS1 est au début de la chaîne S. Par conséquent, S1 n’apparaîtra pas après la sous-chaîne S2.

Entrez – S = « abce », S1 = « bc », S2 = « xy »

Sortie – Non

Explication – Puisque la chaîne S2 n'existe pas dans la chaîne S, imprimez le numéro.

Méthode 1

Dans cette méthode, nous trouverons tous les indices de départ des sous-chaînes S2 et les stockerons dans une collection. Après cela, nous obtiendrons l’indice de départ de S1. Nous comparons chaque index de départ de S2 avec l'index de départ de S1 et si nous trouvons qu'une valeur dans l'ensemble est inférieure à l'index de départ de S2, alors nous pouvons dire que la sous-chaîne S1 apparaît après toute occurrence de la sous-chaîne S2 .

Algorithme

• Définissez la collection qui stocke l'index de départ de la sous-chaîne S2.

• Utilisez la méthode find() pour trouver le premier index de départ de la sous-chaîne S2.

• Utilisez une boucle while pour obtenir tous les indices de départ de la sous-chaîne S2 et stockez-les dans une collection à l'aide de la méthode insert().

• Parcourez les valeurs définies. Renvoie vrai si une valeur est inférieure à l'index de départ de la sous-chaîne S1 dans la chaîne S donnée.

• Renvoie enfin false.

Exemple

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
bool isS1AfterS2(string& S, string& S1, string& S2) {
   // set to store indices of S2 in S
   unordered_set<int> indices;
   // Find all occurrences of S2 in S, and store them in set
   size_t found = S.find(S2);
   while (found != string::npos) {
      indices.insert(found);
      found = S.find(S2, found + 1);
   }
   // Compare starting indices of S1 with S2
   for (const int& index : indices) {
      if (index < S.find(S1)) {
          return true;  // S2 appears before S1
      }
   }
   return false;  // S1 appears before or at the same position as S2
}
int main(){
   string S = "abxtutorialspointwelcomepoint";
   string S1 = "welcome", S2 = "point";
   if(isS1AfterS2(S, S1, S2)) {
          cout << "Yes, string S1 appears after string S2.";
   } else { 
      cout << "No, string S1 does not appear after string S2.";
   }
   return 0;
}

Sortie

Yes, string S1 appears after string S2.

Complexité temporelle - O(N*K), car nous devons trouver l'index de départ de la chaîne S2.

Complexité spatiale - O(N) puisque nous stockons l'index de départ de la chaîne S2.

Méthode 2

Dans cette méthode, nous allons parcourir la chaîne. Renvoie vrai si nous constatons que S2 se produit avant S1 car la chaîne S contient toujours la chaîne S1.

Algorithme

• Définissez les variables len, n1 et n2 pour stocker la longueur de la variable.

• Commencez à parcourir la chaîne.

• Définissez la 'chaîne temporaire et initialisez-la avec une sous-chaîne de longueur n2 commençant au i-ième index.

• Si temp == S2, renvoie vrai.

• Obtenez une sous-chaîne de longueur n1 à partir du i-ième index. Si temp == s1, renvoie false.

• Renvoie enfin vrai.

Exemple

#include <bits/stdc++.h>
using namespace std;
bool isS1AfterS2(string &S, string &S1, string &S2){
   // store the length of the strings
   int n1 = S1.size(), n2 = S2.size();
   // Traverse the string S from left to right
   for (int i = 0; i <= S.size() - n2; i++){
      // temporary string to store substring
      string temp;
      // get the substring
      temp = S.substr(i, n2);
      // if we find the string S2, return true as s1 always present in s.
      if (temp == S2){
          return true;
      }
      temp = S.substr(i, n1);
      // If we find s1 before s2, return false
      if (temp == S1){
          return false;
      }
   }
   return true;
}
int main(){
   string S = "abxtutorialspointwelcome";
   string S1 = "welcome", S2 = "point";
   if(isS1AfterS2(S, S1, S2)) {
      cout << "Yes, string S1 appears after string S2.";
   } else { 
      cout << "No, string S1 does not appear after string S2.";
   }
   return 0;
}

Sortie

Yes, string S1 appears after string S2.

Complexité temporelle – O(N*min(n1, n2)), puisque nous trouvons des sous-chaînes de longueur n1 et n2.

Complexité spatiale - O(min(n1, n2) puisque nous stockons des sous-chaînes.

Dans la première méthode, nous utilisons une collection pour stocker l'index de départ de S2, ce qui nécessite plus d'espace que le code de la deuxième méthode. Le code de la deuxième méthode est plus lisible que celui de la première méthode. Alternativement, les programmeurs peuvent essayer de résoudre le problème de vérifier si la sous-chaîne S2 apparaît après l'apparition de S1.

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!