Find different palindromic substrings in a given string using dynamic programming

introduce

In this tutorial, we discussed a method to find all possible palindromic substrings using an input string. To implement the method for this task we use C programming language and its functions.

A palindrome is a string that reads the same from front to back and from back to front. For example, Mom is a palindrome string. In this tutorial, we will take a string and find all possible palindrome substrings in it.

The Chinese translation of

Example 1

is:

Example 1

String = abcaa

Output

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

In the above example, the input string can generate 7 palindrome substrings: 'a', 'b', 'c', 'aa', 'aaa', 'aba' and 'aca'.

The Chinese translation of

Example 2

is:

Example 2

String = “abcd”

Output

a, b, c, and d.

In the above example, only 4 palindromic substrings of length 1 can be obtained using the input string. Since there are no repeated characters in the input string, no substring has a length greater than 1.

Function used for example implementation

• size() − This is a string-like function that returns the number of characters in a given string. It does not accept parameters.

grammar

string_name.size();

Example

str.size();

• begin() − This library function is defined in STL. It gives the starting iteration value of the map container.

Syntax: map_name.begin(); Example: mp.begin();

• end() − This library function is defined in STL. It gives the end iteration value of the map container.

grammar

map_name.end();

Example

mp.end();

• substr() − It generates a substring using the input string. It is defined in the string.h header file. It accepts two parameters (pos, len). Pos is the starting value of the substring and len is the number of characters in the substring.

grammar

string_name.substr(pos, len);

Example

str.substr();

algorithm

• Consider a given string and find all palindrome substrings in it.

• Find all palindromic substrings of the input string by iterating the string.

• Create two arrays for odd and even length palindromic substrings.

• Store the values ​​of two arrays in a hash map.

• Print all values ​​stored in Hashmap.

• The number of substrings is equal to the length of the hash map. Iterate through the hash map and print out each value. Use a for loop to access each item in the map and print its associated value. Finally, the number of values ​​printed should match the size of the hash map.

Logic 1 Example

In this section, we implement one of the above examples using concepts from the C programming language. We consider an input string in the main() function and use it to generate output.

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

Output

Palindrome substrings are listed as:
a
aa
b
c

Logic 2 Example

We are implementing another example using dynamic programming methods. In dynamic programming, tasks are broken down into subtasks and solved individually to reduce time and complexity.

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

Output

a
aba
b
aa
Total number of palindromes are 4

in conclusion

In this tutorial, we developed two methods to find all possible palindromic substrings in a given string. We use two examples to understand the task and write a sample code using C programming language. We use hash maps and vectors to store palindromic substrings to implement the example. The use of hash map helps in matching key value pairs and we can use many hash functions as per our requirement. We also used some library functions to implement the examples.

The above is the detailed content of Find different palindromic substrings in a given string using dynamic programming. For more information, please follow other related articles on the PHP Chinese website!