Bilangan minimum awalan dan akhiran yang diperlukan untuk membentuk rentetan tertentu

Awalan ialah subrentetan dalam rentetan yang diberikan, bermula pada indeks sifar dan sehingga saiz rentetan. Begitu juga, akhiran ialah sebarang subrentetan panjang 1 hingga saiz rentetan, berakhir pada indeks terakhir. Kami akan diberikan dua rentetan dan rentetan pertama mesti dibuat dalam apa cara sekalipun menggunakan sebarang bilangan awalan dan akhiran daripada rentetan kedua. Jika rentetan yang diberikan tidak boleh dibuat daripada kaedah yang diberikan, maka kami akan mengembalikan -1.

Contoh

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

Output:  2

Terjemahan bahasa Cina bagi

Penjelasan

ialah:

Penjelasan

Kita boleh menggunakan awalan "titik" dan akhiran "tutorial", dan dengan menggabungkannya, kita boleh mendapatkan rentetan pertama. Ini hanya memerlukan dua subrentetan dan ini adalah jawapan atau output kami.

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

Output: -1

Terjemahan bahasa Cina bagi

Penjelasan

ialah:

Penjelasan

Kami tidak boleh mendapatkan rentetan pertama daripada akhiran atau awalan rentetan kedua yang diberikan.

Kaedah

Untuk menyelesaikan masalah ini, kami akan menggunakan konsep pengaturcaraan dinamik, yang diselesaikan dengan menyimpan kejadian yang telah berlaku.

• Pertama, kami akan mencipta fungsi yang akan mengambil dua rentetan sebagai parameter dan mengembalikan integer.

• Dalam fungsi ini, mula-mula kita akan mendapatkan panjang rentetan dan mencipta set cincang dan rentetan sementara untuk mendapatkan awalan.

• Kami akan melelar melalui rentetan kedua dan mendapatkan semua awalan dan menyimpannya dalam set cincang. Begitu juga, dengan melintasi rentetan dari belakang ke hadapan, kita boleh mendapatkan semua akhiran dan menyimpannya dalam set cincang.

• Kemudian kami akan mencipta tatasusunan untuk menyimpan hasil pengaturcaraan dinamik dan menyimpan -1 pada setiap kedudukan indeks tatasusunan.

• Menggunakan gelung bersarang, kami membahagi rentetan pertama kepada ketulan dan mencari sama ada kami boleh menggabungkan semua ketulan dalam peta cincang.

• Kami akan cuba sedaya upaya untuk mengurangkan bilangan substring yang diperlukan, jika ini tidak mungkin, -1 akan dikembalikan.

Contoh

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

Output

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

Kerumitan masa dan ruang

Kerumitan masa kod di atas ialah O(N^2) kerana kerumitan semua akhiran yang kami dapat adalah tinggi, tetapi kerumitan masa boleh dikurangkan dengan membalikkan rentetan. Selain itu, kami menyimpan rentetan ke dalam set cincang menjadikan kerumitan masa tinggi, dan sarang untuk gelung untuk pengaturcaraan dinamik.

Kerumitan ruang kod di atas ialah O(N^2) kerana kami menyimpan semua akhiran dan awalan dalam peta cincang.

Kesimpulan

Dalam tutorial ini, kami melaksanakan kod untuk mencari bilangan minimum subrentetan dalam akhiran dan awalan rentetan yang diberikan untuk mencipta rentetan lain yang diberikan, jika tidak boleh, kami mencetak -1. Kami menggunakan konsep pengaturcaraan dinamik dengan menyimpan elemen dalam set cincang dan kemudian menggunakan gelung bersarang dengan kerumitan masa dan ruang O(N^2).

Atas ialah kandungan terperinci Bilangan minimum awalan dan akhiran yang diperlukan untuk membentuk rentetan tertentu. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!