Find all distinct palindromic sub | C ++ program to find all distinct palindrome sub - strings of a given string ; Function to print all distinct palindrome sub - strings of s ; table for storing results ( 2 rows for odd - and even - length palindromes ; Find all sub - string palindromes from the given input string insert ' guards ' to iterate easily over s ; int rp = 0 ; length of ' palindrome ▁ radius ' ; Attempt to expand palindrome centered at i ; Assigning the found palindromic length to odd / even length array ; remove ' guards ' ; Put all obtained palindromes in a hash map to find only distinct palindromess ; printing all distinct palindromes from hash map ; Driver program
#include <iostream> NEW_LINE #include <map> NEW_LINE using namespace std ; void palindromeSubStrs ( string s ) { map < string , int > m ; int n = s . size ( ) ; int R [ 2 ] [ n + 1 ] ; s = " @ " + s + " # " ; for ( int j = 0 ; j <= 1 ; j ++ ) { R [ j ] [ 0 ] = 0 ; int i = 1 ; while ( i <= n ) { while ( s [ i - rp - 1 ] == s [ i + j + rp ] ) R [ j ] [ i ] = rp ; int k = 1 ; while ( ( R [ j ] [ i - k ] != rp - k ) && ( k < rp ) ) { R [ j ] [ i + k ] = min ( R [ j ] [ i - k ] , rp - k ) ; k ++ ; } rp = max ( rp - k , 0 ) ; i += k ; } } s = s . substr ( 1 , n ) ; m [ string ( 1 , s [ 0 ] ) ] = 1 ; for ( int i = 1 ; i <= n ; i ++ ) { for ( int j = 0 ; j <= 1 ; j ++ ) for ( int rp = R [ j ] [ i ] ; rp > 0 ; rp -- ) m [ s . substr ( i - rp - 1 , 2 * rp + j ) ] = 1 ; m [ string ( 1 , s [ i ] ) ] = 1 ; } cout << " Below ▁ are ▁ " << m . size ( ) - 1 << " ▁ palindrome ▁ sub - strings " ; map < string , int > :: iterator ii ; for ( ii = m . begin ( ) ; ii != m . end ( ) ; ++ ii ) cout << ( * ii ) . first << endl ; } int main ( ) { palindromeSubStrs ( " abaaa " ) ; return 0 ; }