## Wednesday, January 6, 2016

### Find all distinct palindromic sub-strings of a given string - GeeksforGeeks

Find all distinct palindromic sub-strings of a given string - GeeksforGeeks
Given a string of lowercase ASCII characters, find all distinct continuous palindromic sub-strings of it.
```Input: str = "abaaa"
Output:  Below are 5 palindrome sub-strings
a
aa
aaa
aba
b```
Step 1: Finding all palindromes using modified Manacher’s algorithm:
Considering each character as a pivot, expand on both sides to find the length of both even and odd length palindromes centered at the pivot character under consideration and store the length in the 2 arrays (odd & even).
Time complexity for this step is O(n^2)
Step 2: Inserting all the found palindromes in a HashMap:
Insert all the palindromes found from the previous step into a HashMap. Also insert all the individual characters from the string into the HashMap (to generate distinct single letter palindromic sub-strings).
Time complexity of this step is O(n^3) assuming that the hash insert search takes O(1) time. Note that there can be at most O(n^2) palindrome sub-strings of a string. In below C++ code ordered hashmap is used where the time complexity of insert and search is O(Logn). In C++, ordered hashmap is implemented using Red Black Tree.
Step 3: Printing the distinct palindromes and number of such distinct palindromes:
`void` `palindromeSubStrs(string s)`
`{`
`    ``map<string, ``int``> m;`
`    ``int` `n = s.size();`
`    ``// table for storing results (2 rows for odd-`
`    ``// and even-length palindromes`
`    ``int` `R[2][n+1];`
`    ``// Find all sub-string palindromes from the given input`
`    ``// string insert 'guards' to iterate easily over s`
`    ``s = ``"@"` `+ s + ``"#"``;`
`    ``for` `(``int` `j = 0; j <= 1; j++)`
`    ``{`
`        ``int` `rp = 0;   ``// length of 'palindrome radius'`
`        ``R[j][0] = 0;`
`        ``int` `i = 1;`
`        ``while` `(i <= n)`
`        ``{`
`            ``//  Attempt to expand palindrome centered at i`
`            ``while` `(s[i - rp - 1] == s[i + j + rp])`
`                ``rp++;  ``// Incrementing the length of palindromic`
`                       ``// radius as and when we find vaid palindrome`
`            ``// Assigning the found palindromic length to odd/even`
`            ``// length array`
`            ``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;`
`        ``}`
`    ``}`
`    ``// remove 'guards'`
`    ``s = s.substr(1, n);`
`    ``// Put all obtained palindromes in a hash map to`
`    ``// find only distinct palindromess`
`    ``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;`
`    ``}`
`    ``//printing all distinct palindromes from hash map`
`   ``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;`
`}`
http://www.techiedelight.com/find-possible-palindromic-substrings-string/
We can solve this problem in O(n2) time and O(1) space. The idea is inspired from Longest Palindromic Substring problem. For each character in the given string, we consider it as mid point of a palindrome and expand in both directions to find all palindromes that have it as mid-point. For even length palindrome, we consider every adjacent pair of characters as mid point. We use a set to store all unique palindromic substrings.
void expand(string str, int low, int high, auto &set)
{
// run till str[low.high] is a palindrome
while (low >= 0 && high < str.length()
&& str[low] == str[high])
{
// push all palindromes into the set
set.insert(str.substr(low, high - low + 1));

// expand in both directions
low--, high++;
}
}

// Function to find all unique palindromic substrings of given string
void allPalindromicSubstrings(string str)
{
// create an empty set to store all unique palindromic substrings
unordered_set<string> set;

for (int i = 0; i < str.length(); i++)
{
// find all odd length palindrome with str[i] as mid point
expand(str, i, i, set);

// find all even length palindrome with str[i] and str[i+1] as
// its mid points
expand(str, i, i + 1, set);
}

// print all unique palindromic substrings
for (auto i : set)
cout << i << " ";
}

http://siyang2notleetcode.blogspot.com/2015/02/finding-all-palindromes-in-string.html

https://discuss.leetcode.com/topic/90/count-palindromes
Count the number of possible palindrome substrings in a string. A palindrome is a word that reads the same way spelled backwards.
Example:
input: lasagna.
Possible palindromes are asa, l,a,s,a,g,n,a.
output: count is 8.
input:hellolle
ellolle,lloll,lol,ll,ll,h,e,l,l,o,l,l,e.
output:13
https://discuss.leetcode.com/topic/35753/print-all-the-palindromic-substrings-of-a-given-string

http://www.geeksforgeeks.org/count-palindrome-sub-strings-string/
Given a string, the task is to count all palindrome substring in a given string. Length of palindrome substring is greater then or equal to 2.

`    ``static` `int` `CountPS(``char` `str[], ``int` `n)`
`    ``{`
`        ``// creat empty 2-D matrix that counts all palindrome`
`        ``// substring. dp[i][j] stores counts of palindromic`
`        ``// substrings in st[i..j]`
`        ``int` `dp[][] = ``new` `int``[n][n];`
`     `
`        ``// P[i][j] = true if substring str[i..j] is palindrome,`
`        ``// else false`
`        ``boolean` `P[][] = ``new` `boolean``[n][n];`
`     `
`        ``// palindrome of single lenght`
`        ``for` `(``int` `i= ``0``; i< n; i++)`
`            ``P[i][i] = ``true``;`
`     `
`        ``// palindrome of length 2`
`        ``for` `(``int` `i=``0``; i<n-``1``; i++)`
`        ``{`
`            ``if` `(str[i] == str[i+``1``])`
`            ``{`
`                ``P[i][i+``1``] = ``true``;`
`                ``dp[i][i+``1``] = ``1` `;`
`            ``}`
`        ``}`
`     `
`        ``// Palindromes of length more then 2. This loop is similar`
`        ``// to Matrix Chain Multiplication. We start with a gap of`
`        ``// length 2 and fill DP table in a way that gap between`
`        ``// starting and ending indexes increases one by one by`
`        ``// outer loop.`
`        ``for` `(``int` `gap=``2` `; gap<n; gap++)`
`        ``{`
`            ``// Pick starting point for current gap`
`            ``for` `(``int` `i=``0``; i<n-gap; i++)`
`            ``{`
`                ``// Set ending point`
`                ``int` `j = gap + i;`
`     `
`                ``// If current string is palindrome`
`                ``if` `(str[i] == str[j] && P[i+``1``][j-``1``] )`
`                    ``P[i][j] = ``true``;`
`     `
`                ``// Add current palindrome substring ( + 1)`
`                ``// and rest palinrome substring (dp[i][j-1] + dp[i+1][j])`
`                ``// remove common palinrome substrings (- dp[i+1][j-1])`
`                ``if` `(P[i][j] == ``true``)`
`                    ``dp[i][j] = dp[i][j-``1``] + dp[i+``1``][j] + ``1` `- dp[i+``1``][j-``1``];`
`                ``else`
`                    ``dp[i][j] = dp[i][j-``1``] + dp[i+``1``][j] - dp[i+``1``][j-``1``];`
`            ``}`
`        ``}`
`     `
`        ``// return total palindromic substrings`
`        ``return` `dp[``0``][n-``1``];`
`    ``}`