首頁  >  文章  >  後端開發  >  使用動態規劃找出給定字串中的不同回文子串

使用動態規劃找出給定字串中的不同回文子串

WBOY
WBOY轉載
2023-08-26 10:29:21588瀏覽

使用動態規劃找出給定字串中的不同回文子串

介紹

在本教程中,我們討論了一種使用輸入字串找到所有可能的回文子字串的方法。為了實現這個任務的方法,我們使用C 程式語言及其函數。

回文是一種從前往後和從後往前讀都一樣的字串。例如,Mom是一個回文字串。在本教程中,我們將取一個字串並找出其中所有可能的回文子字串。

Example 1

的中文翻譯為:

範例1

#
String = abcaa

輸出

The possible palindromic substrings are : a, b, c, aa, aaa, aba, and aca.

在上面的例子中,輸入字串可以產生7個回文子字串:‘a’,‘b’,‘c’,‘aa’,‘aaa’,‘aba’和‘aca’。

Example 2

的中文翻譯為:

範例2

String = “abcd”

輸出

a, b, c, and d.

在上面的範例中,使用輸入字串只能得到4個長度為1的回文子字串。由於輸入字串中沒有重複的字符,因此沒有任何子字串的長度超過1。

用於範例實作的函數

  • size() − 這是一個字串類別函數,傳回給定字串中字元的數量。它不接受參數。

文法

string_name.size();

範例

str.size();
  • begin() − 這個函式庫函數在STL中定義。它給出了map容器的起始迭代值。

  • 語法:map_name.begin(); 範例:mp.begin();
  • end() − 這個函式庫函數在STL中定義。它給出了map容器的結束迭代值。

#文法

map_name.end();

範例

mp.end();
  • substr() − 它使用輸入字串產生一個子字串。它在string.h頭檔中定義。它接受兩個參數(pos,len)。 Pos是子字串的起始值,len是子字串中的字元數。

文法

string_name.substr(pos, len);

範例

str.substr();

演算法

  • 考慮一個給定的字串,找出其中所有的回文子字串。

  • 透過迭代字串,找到輸入字串的所有回文子字串。

  • 為奇數和偶數長度的回文子字串建立兩個陣列。

  • 將兩個陣列的值儲存在雜湊映射中。

  • 列印儲存在Hashmap中的所有值。

  • 子字串的數量等於雜湊映射的長度。透過哈希映射進行迭代,並列印出每個值。使用for循環存取映射中的每個項,並列印其關聯的值。最後,列印的值的數量應與哈希映射的大小相符。

Logic 1 範例

在這個部分中,我們使用C 程式語言的概念實作了上面的一個例子。我們在main()函數中考慮一個輸入字串,並使用它來產生輸出。

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

//user defined program to find the palindrome substrings
void palindromeSubStrings(string str){
   map<string, int> mp;
   int l = str.size();
   
   //store odd and even length palindrome substrings
   int R[2][l+1];
   
   //Using guards for effortless iteration over the input string and generating all palindrome
   // substrings
   str = "@" + str + "#";
   
   for (int i = 0; i <= 1; i++) {
      int r = 0;  
      R[i][0] = 0;

      int x = 1;
      while (x <= l){
            
         while (str[x - r - 1] == str[x + i + r])
            r++; 
           
         R[i][x] = r;
         int a = 1;
         while ((R[i][x - a] != r - a) && (a < r)){
            R[i][x + a] = min(R[i][x - a],r - a);
            a++;
         }
         r = max(r - a,0);
         x += a;
      }
   }
   //storing the substring without guards
   str = str.substr(1, l);
      
   mp[string(1, str[0])]=1;
   for (int x = 1; x <= l; x++){
      for (int y = 0; y <= 1; y++)
            for (int r = R[y][x]; r > 0; r--)
               mp[str.substr(x - r - 1, 2 * r + y)]=1;
         mp[string(1, str[x])]=1;
   }
      
   //print the palindrome substrings stored in the Hashmap
   cout << "Palindrome substrings are as listed: ";
   map<string, int>::iterator xx;
   for (xx = mp.begin(); xx!=mp.end(); ++xx)
      cout << (*xx).first << endl;
}
   
//Controlling code
int main(){
   //calling the user-defined function and passing a string as argument
   palindromeSubStrings("abcaa");
   return 0;
}

輸出

Palindrome substrings are listed as:
a
aa
b
c

Logic 2 範例

我們正在使用動態規劃方法實作另一個範例。在動態規劃中,任務被分解為子任務並單獨解決,以減少時間和複雜度。

#include <iostream>
#include <vector>
using namespace std;
//User defined function to find the palindromic substring 
int find(string str){
   int a = str.size();
   //defined dpg array
      vector<vector<bool> > dpg(a, vector<bool>(a, false));
      for (int x = 0; x < a; x++) {

         dpg[x][x] = 1;
  
         if (x < a && str[x] == str[x + 1]) {
            dpg[x][x + 1] = 1;
         }
      }
   // Finding length of different substrings
   for (int l = 3; l <= a; l++) {
      for (int x = 0; x + l - 1 < a; x++){
         if (str[x] == str[x + (l - 1)]
         && dpg[x + 1][x + (l - 1) - 1]) {
            dpg[x][x + (l - 1)] = true;
         }
      }
   }
 
 
   vector<int> kmp(a, 0);
   for (int x = 0; x < a; x++) {
     
      int y = 0, m = 1;
      while (m + x < a) {
         if (str[y + x] == str[m + x]){
            dpg[m + x - y][m + x] = false;
            kmp[m++] = ++y;
         }
         else if (y > 0) {
            y = kmp[y - 1];
         }
         else {
            kmp[m++] = 0;
         }
      }
   }

   int cnt = 0;
   for (int x = 0; x < a; x++) {
      string str1;
      for (int y = x; y < a; y++) {
         str1 += str[y];
         if (dpg[x][y]) {
            //counting number of palindromic substrings formed using the string
               cnt++;
               cout << str1 << '\n';
         }
      }
   }
   cout << "Total number of palindromes are "
   << cnt << '\n';
   return 0;
}
 
//Controller
int main(){
   string str = "abaa";
   find(str);
   return 0;
}

輸出

a
aba
b
aa
Total number of palindromes are 4

結論

在本教程中,我們開發了兩種方法來尋找給定字串中所有可能的回文子字串。我們透過兩個範例來理解任務,並使用C 程式語言編寫了一個範例程式碼。我們使用哈希映射和向量來儲存回文子字串以實現範例。哈希映射的使用有助於匹配鍵值對,我們可以根據需要使用許多雜湊函數。我們也使用了一些函式庫函數來實作範例。

以上是使用動態規劃找出給定字串中的不同回文子串的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文轉載於:tutorialspoint.com。如有侵權,請聯絡admin@php.cn刪除