Le nombre minimum de préfixes et suffixes requis pour former une chaîne donnée

Le préfixe est une sous-chaîne dans la chaîne donnée, commençant à l'index zéro et jusqu'à la taille de la chaîne. De même, le suffixe est toute sous-chaîne de longueur 1 à la taille de la chaîne, se terminant au dernier index. Nous recevrons deux chaînes et la première chaîne doit être créée de quelque manière que ce soit en utilisant n'importe quel nombre de préfixes et suffixes de la deuxième chaîne. Si la chaîne donnée ne peut pas être créée à partir de la méthode donnée, alors nous renverrons -1.

Exemple

Input 1: string str1 = “tutorialspoint”  string str2 = “pointstutorial”

Output:  2

Explication

Explication

On peut utiliser le préfixe "points" et le suffixe "tutorial", et en les concaténant, on peut obtenir la première chaîne. Cela ne nécessite que deux sous-chaînes et c'est notre réponse ou sortie.

Input 2: string str1 = “randomstring” string str2 = “anotherstring” 

Output: -1

Explication

Explication

Nous ne pouvons pas obtenir la première chaîne à partir du suffixe ou du préfixe donné de la deuxième chaîne.

Méthode

Pour résoudre ce problème, nous utiliserons le concept de programmation dynamique, qui est résolu en stockant les instances déjà survenues.

• Tout d'abord, nous allons créer une fonction qui prendra deux chaînes comme paramètres et renverra un entier.

• Dans cette fonction, nous allons d'abord obtenir la longueur de la chaîne et créer un jeu de hachage et une chaîne temporaire pour obtenir le préfixe.

• Nous allons parcourir la deuxième chaîne, obtenir tous les préfixes et les stocker dans un jeu de hachage. De même, en parcourant la chaîne d’arrière en avant, nous pouvons obtenir tous les suffixes et les stocker dans un jeu de hachage.

• Ensuite, nous créerons un tableau pour stocker les résultats de la programmation dynamique et stockerons -1 à chaque position d'index du tableau.

• En utilisant des boucles for imbriquées, nous divisons la première chaîne en morceaux et déterminons si nous pouvons concaténer tous les morceaux dans la carte de hachage.

• Nous ferons de notre mieux pour réduire le nombre de sous-chaînes requises, si cela n'est pas possible, -1 sera renvoyé.

Exemple

#include <bits/stdc++.h>
using namespace std;
// function to find the required number of substrings
int count(string str1, string str2){
   unordered_set<string> st; // set to store the strings from the prefix and suffix 
   string temp = "";// string to store the prefixes and suffixes 
   int len1 = str1.size(); // size of the first string 
   int len2 = str2.size(); // getting size of the second 
   
   // getting prefixes of string second 
   for (int i = 0; i < len2; i++){
      temp += str2[i]; // adding the characters to temporary string
      st.insert(temp); // insert current string to set 
   }
   
   // getting all the sufixes 
   for (int i = len2-1; i >= 0; i--){
      temp = str2.substr(i); // getting suffixes		
      st.insert(temp); // adding suffixes to the set 
   }
   // Initialize memo array to store the answer
   int memo[len1+1];
   memset(memo, -1, sizeof(memo)); // initializing array 
   memo[0] = 0; 
   
   // applying the concepts of dp 
   // traversing over the main string and will try to 
   // partition string into chunks 
	for (int i = 0; i < len1; i++){
      for (int j = 1; j <= len1 - i; j++){
		   // check if the set contain current substring 
         if (st.find(str1.substr(i, j)) != st.end()){
            if (memo[i] == -1){
               continue;
            }
            if (memo[i + j] == -1){
               memo[i + j] = memo[i] + 1;
            }
            else {
               memo[i + j] = min(memo[i + j], memo[i] + 1);
            }
         }
      }
   }
   // Return the answer
   return memo[len1];
}
int main(){
   string str1 = "tutorialpoints";
   string str2 = "pointstutorial";
   // calling function to find the minimum number of substrings required
   cout <<"The minimum count of prefixes and suffixes of a string required to form given string is "<<count(str1, str2)<<endl;
   return 0;
}

Sortie

The minimum count of prefixes and suffixes of a string required to form given string is 2

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N^2) car la complexité de tous les suffixes que nous obtenons est élevée, mais la complexité temporelle peut être réduite en inversant la chaîne. De plus, nous stockons les chaînes dans des jeux de hachage, ce qui rend la complexité temporelle élevée, et nous imbriquons des boucles pour une programmation dynamique.

La complexité spatiale du code ci-dessus est O(N^2) car nous stockons tous les suffixes et préfixes dans une carte de hachage.

Conclusion

Dans ce tutoriel, nous avons implémenté un code pour trouver le nombre minimum de sous-chaînes dans le suffixe et le préfixe d'une chaîne donnée pour créer une autre chaîne donnée, si ce n'est pas possible, nous imprimons -1. Nous avons utilisé le concept de programmation dynamique en stockant les éléments dans un jeu de hachage, puis en utilisant des boucles imbriquées avec une complexité temporelle et spatiale de O(N^2).

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!