Count pairs of non-overlapping palindromic sub-strings of the given string

In this post, we will write a program to count the pairs of non-lapping palindromic sub-strings of an array, this code will be written in C++ programming language.

Here is the C++ program to Count pairs of non-overlapping palindromic sub-strings of the given string:

 

#include <bits/stdc++.h>
using namespace std;

#define N 100

void pre_process(bool dp[N][N], string s)
{      

    int n = s.size();          

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            dp[i][j] = false;
    }      
    for (int j = 1; j <= n; j++) {                  
        for (int i = 0; i <= n - j; i++) {              
            if (j <= 2) {                  
                if (s[i] == s[i + j - 1])
                    dp[i][i + j - 1] = true;
            }              
            else if (s[i] == s[i + j - 1])
                dp[i][i + j - 1] = dp[i + 1][i + j - 2];
        }
    }
}  

int countPairs(string s)
{      
    bool dp[N][N];
    pre_process(dp, s);
    int n = s.length();      
    int left[n];
    memset(left, 0, sizeof left);      
    int right[n];
    memset(right, 0, sizeof right);      
    left[0] = 1;          
    for (int i = 1; i < n; i++) {  
        for (int j = 0; j <= i; j++) {  
            if (dp[j][i] == 1)
                left[i]++;
        }
    }      
    right[n - 1] = 1;          
    for (int i = n - 2; i >= 0; i--) {  
        right[i] = right[i + 1];  
        for (int j = n - 1; j >= i; j--) {  
            if (dp[i][j] == 1)
                right[i]++;
        }
    }  
    int ans = 0;      
    for (int i = 0; i < n - 1; i++)
        ans += left[i] * right[i + 1];  
    return ans;
}
int main()
{
    string s = "abacaba";
    cout << countPairs(s); 
    return 0;
}

Output:

36

Leave a Comment