Die Mindestanzahl an Präfixen und Suffixen, die zum Bilden einer bestimmten Zeichenfolge erforderlich sind

Das Präfix ist eine Teilzeichenfolge in der angegebenen Zeichenfolge, beginnend beim nullten Index und bis zur Größe der Zeichenfolge. Ebenso ist das Suffix ein beliebiger Teilstring mit einer Länge von 1 bis zur Größe des Strings, der am letzten Index endet. Wir erhalten zwei Zeichenfolgen und die erste Zeichenfolge muss auf beliebige Weise unter Verwendung einer beliebigen Anzahl von Präfixen und Suffixen aus der zweiten Zeichenfolge erstellt werden. Wenn die angegebene Zeichenfolge nicht mit der angegebenen Methode erstellt werden kann, geben wir -1 zurück.

Beispiel

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

Output:  2

Erklärung

Erklärung

Wir können das Präfix „points“ und das Suffix „tutorial“ verwenden und durch ihre Verkettung die erste Zeichenfolge erhalten. Dafür sind nur zwei Teilzeichenfolgen erforderlich und dies ist unsere Antwort oder Ausgabe.

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

Output: -1

Erklärung

Erklärung

Wir können die erste Zeichenfolge nicht aus dem angegebenen Suffix oder Präfix der zweiten Zeichenfolge erhalten.

Methode

Um dieses Problem zu lösen, verwenden wir das Konzept der dynamischen Programmierung, das durch die Speicherung der bereits aufgetretenen Instanzen gelöst wird.

• Zuerst erstellen wir eine Funktion, die zwei Zeichenfolgen als Parameter akzeptiert und eine Ganzzahl zurückgibt.

• In dieser Funktion ermitteln wir zunächst die Länge der Zeichenfolge und erstellen einen Hash-Satz und eine temporäre Zeichenfolge, um das Präfix zu erhalten.

• Wir durchlaufen die zweite Zeichenfolge, erhalten alle Präfixe und speichern sie in einem Hash-Set. Ebenso können wir durch das Durchlaufen der Zeichenfolge von hinten nach vorne alle Suffixe erhalten und sie in einem Hash-Set speichern.

• Anschließend erstellen wir ein Array zum Speichern der Ergebnisse der dynamischen Programmierung und speichern -1 an jeder Indexposition des Arrays.

• Mithilfe verschachtelter for-Schleifen teilen wir die erste Zeichenfolge in Blöcke auf und finden heraus, ob wir alle Blöcke in der Hash-Map verketten können.

• Wir werden unser Bestes tun, um die Anzahl der erforderlichen Teilzeichenfolgen zu reduzieren. Wenn dies nicht möglich ist, wird -1 zurückgegeben.

Beispiel

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

Ausgabe

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

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt O(N^2), da die Komplexität aller Suffixe, die wir erhalten, hoch ist, aber die zeitliche Komplexität kann durch Umkehren der Zeichenfolge reduziert werden. Darüber hinaus speichern wir Zeichenfolgen in Hash-Sets, was die zeitliche Komplexität erhöht, und verschachteln for-Schleifen für dynamische Programmierung.

Die räumliche Komplexität des obigen Codes beträgt O(N^2), da wir alle Suffixe und Präfixe in einer Hash-Map speichern.

Fazit

In diesem Tutorial haben wir einen Code implementiert, um die Mindestanzahl von Teilzeichenfolgen im Suffix und Präfix einer bestimmten Zeichenfolge zu ermitteln, um eine andere bestimmte Zeichenfolge zu erstellen. Wenn dies nicht möglich ist, geben wir -1 aus. Wir nutzten das Konzept der dynamischen Programmierung, indem wir die Elemente in einem Hash-Set speicherten und dann verschachtelte Schleifen mit einer zeitlichen und räumlichen Komplexität von O(N^2) verwendeten.

Das obige ist der detaillierte Inhalt vonDie Mindestanzahl an Präfixen und Suffixen, die zum Bilden einer bestimmten Zeichenfolge erforderlich sind. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!