C++ 使用动态规划查找给定字符串的不同回文子串

介绍

在这个教程中，我们讨论了一种查找输入字符串中所有可能的回文子串的方法。为了实现这个任务，我们使用C++编程语言和其函数。

回文是一个从后往前阅读和前往后阅读相同的字符串。例如，Mom是一个回文字符串。在本教程中，我们接收一个字符串并找出其中所有可能的回文子串。

示例1

String = abcaa

输出

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

在上面的示例中，输入字符串可以生成7个回文子字符串：‘a’，‘b’，‘c’，‘aa’，‘aaa’，‘aba’和‘aca’。

示例2

String = “abcd”

输出

a, b, c, and d.

在上面的示例中，使用输入字符串只有4个长度为1的回文子字符串。由于输入字符串中没有重复的字符，所以没有子字符串的长度超过1。

用于示例实现的函数

• size() − 这是一个字符串类函数，返回给定字符串中字符的数量，即字符串的长度。它不接受参数。

语法

string_name.size();

示例

str.size();

• begin() − 此库函数在STL中定义。它给出映射容器的起始迭代值。

语法：map_name.begin(); 示例：mp.begin();
* end() − 此库函数在STL中定义。它给出映射容器的结束迭代值。

语法

map_name.end();

示例

mp.end();

• substr()函数 - 使用输入的字符串生成一个子字符串。它在string.h头文件中定义。它接受两个参数（pos，len）。pos是子字符串的起始值，len是子字符串中的字符数。

语法

string_name.substr(pos, len);

示例

str.substr();

步骤

• 考虑给定字符串，找出其所有回文子字符串。

• 通过遍历字符串来找出输入字符串的所有回文子字符串。

• 创建两个数组，分别存储奇数长度和偶数长度的回文子字符串。

• 将两个数组的值存储在哈希表中。

• 打印哈希表中存储的所有值。

• 子字符串的数量等于哈希表的长度。遍历哈希表并打印每个值。使用for循环访问哈希表中的每个项并打印其关联的值。最后，打印的值的数量应与哈希表的大小相匹配。

示例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

示例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++编程语言编写了一个代码实现。我们使用哈希映射和向量来存储回文子字符串以实现示例。哈希映射的使用有助于匹配键值对，我们可以根据需要使用许多哈希函数。我们还使用了一些库函数来实现示例。