All distinct substrings in a word are all contiguous sequence of characters within a string with all possible lengths. A suffix trie is a tree-like data structure that store all suffixes in a word. After you build a suffix trie, all distinct substrings of a word can be retrieved easily. A palindromic substring is a substring that read from left to right is equal to the string read from right to left within the word. So to find all distinct palindromic substrings, you just check whether a substring is palindromic when you traverse the suffix trie. In the following example, all distinct palindromic substrings of “lebebe” are “b”, “beb”, “e”, “ebe”, “ebebe” and “l”.
To build a suffix trie, first you define a SuffixTrieNode class which is used to create nodes in a suffix trie. There are 2 variables. children is an array data structure of size 26. The indices are alphabet a-z. Only the cell with the letter in the current node has a value. Then you define a SuffixTrie class which has one variable root. To build a suffix trie from a word, you use the word as the input of the constructor.
insertSuffix method is a recursive function to insert one node (one letter) in a suffix trie. If the input string is null or its length is 0, it is a terminal condition. All recursive calls return to calling functions. Otherwise, you retrieve the first character of the input string. Use the character as the index to check the input node’s children. If there is no value in that cell, create a suffixTrieNode as a child node and save it in that cell. Then the method calls itself with the new node, the substring after the first character.
After you build a suffix trie, you can find all distinct palindromic substrings. You do it by traversing the whole suffix trie. The traversal method uses recursion as well. When the input node is null, it is a terminal condition, you can return. Otherwise you check the input string, which is the substring from the root to the current node. If it is palindromic, you print it. Then you check all cells in the node’s children with the indices letter a-z . If there is a value at one letter, the value is the next node in this branch. The method calls itself using this node and the input string appended with the letter.
Question statement:
Calculate number of DISTINCT palindromic substrings in a string with help of suffix trie.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
public class FindDistinctPalidromicSubstrings { static final int NUM_OF_CHAR = 26; static class SuffixTrieNode{ SuffixTrieNode[] children = new SuffixTrieNode[NUM_OF_CHAR]; } static class SuffixTrie { SuffixTrieNode root; //constructor to build a suffix trie, Time O(s^2), Space O(s) public SuffixTrie(String s) { root = new SuffixTrieNode(); for (int i = 0; i < s.length(); i++) { insertSuffix(root, s.substring(i)); } } //Recursive method to insert suffix node, Time O(s^2), Space O(s) private void insertSuffix(SuffixTrieNode node, String s) { if (s.length() > 0) { char i = (char) (s.charAt(0) - 'a'); if (node.children[i] == null) { node.children[i] = new SuffixTrieNode(); } insertSuffix(node.children[i], s.substring(1)); } } } //Wrapper method to call recursion, Time O(s^2), Space O(s) public static int countPaliSub(String s) { SuffixTrie suffTrie = new SuffixTrie(s); return countPaliSubRec("",suffTrie.root); } //Traverse suffix trie, recursion, Time O(s^2), Space O(s), s is length input string private static int countPaliSubRec(String s, SuffixTrieNode node) { if (node == null) { return 0; } int count = 0; if (isPalindrome(s)) { count ++; System.out.print(s + " "); } for (int k = 0; k < NUM_OF_CHAR; k++) { if (node.children[k] != null) { count += countPaliSubRec(s + (char) (k + 'a'), node.children[k]); } } return count; } //utility function to check whether the string is palindrome, Time O(s), Space O(1) private static boolean isPalindrome(String s) { if (s == null || s.length() == 0 ) return false; int n = s.length(); for (int i = 0; i < n/2; i++) { if (s.charAt(i) != s.charAt(n-i-1)) return false; } return true; } public static void main(String args[]) { String s = "lebebe"; System.out.println("\npalindromic substrings are (suffix trie): "); System.out.println("\ncount is "+ countPaliSub(s)); } } |
JavaScript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
class SuffixTrieNode { constructor() { this.children =[]; } } class SuffixTrie{ //Constructor, Call insertSuffix, Time O(s^2), Space O(s), s is string length constructor(str) { this.root = new SuffixTrieNode(); for (let i = 0; i < str.length; i++) this.insertSuffix(this.root, str.substring(i)); } //Insert a suffix node, Recursion, Time O(s), Space O(s) insertSuffix(node, str) { if (str.length > 0) { let c = str.charAt(0); if (node.children[c] == null) node.children[c] = new SuffixTrieNode(); this.insertSuffix(node.children[c], str.substring(1)); } } } //Wrapper method to call recursion, Time O(s^2), Space O(s) function countPaliSub(s) { var suffTrie = new SuffixTrie(s); return countPaliSubRec("", suffTrie.root); } //Traverse suffix trie,recursion, Time O(s^2), Space O(s), s is length input string function countPaliSubRec(s, node) { if (node == null) { return 0; } var count = 0; if (isPalindrome(s)) { count ++; console.log(s + " "); } for (let k = 97; k < 122; k++) { //letter a to z var letter = String.fromCharCode(k); if (node.children[letter] != null) { count += countPaliSubRec(s + letter, node.children[letter]); } } return count; } //utility function to check whether the string is palindrome, Time O(s), Space O(1) function isPalindrome(s) { if (s == null || s.length == 0 ) return false; var n = s.length; for (let i = 0; i < n/2; i++) { if (s.charAt(i) != s.charAt(n-i-1)) return false; } return true; } let s = "lebebe"; console.log("\npalindromic substrings are (suffix trie): "); console.log("\ncount is "+ countPaliSub(s)); |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
from string import ascii_lowercase class SuffixTrieNode: def __init__(self): self.children =[None]*26 class SuffixTrie : #Constructor, Call insertSuffix, Time O(s^2), Space O(s), s is string length def __init__(self, str): self.root = SuffixTrieNode() for i in range(0, len(str)): self.insertSuffix(self.root, str[i:]) #Insert a suffix node, Recursion, Time O(s), Space O(s) def insertSuffix(self, node, str) : if len(str) > 0 : k = ord(str[0]) -97 if node.children[k] is None: node.children[k] = SuffixTrieNode() self.insertSuffix(node.children[k], str[1:]) #Wrapper method to call recursion, Time O(s^2), Space O(s), def countPaliSub(s) : suffTrie = SuffixTrie(s) return countPaliSubRec("", suffTrie.root) #Traverse suffix trie, recursion, Time O(s^2), Space O(s), s is length input string def countPaliSubRec(s, node): if node is None : return 0 count = 0 if (isPalindrome(s)) : count += 1 print(s + " ") for c in ascii_lowercase: #letter a to z k = ord(c) - 97 if node.children[k] : count += countPaliSubRec(s+c, node.children[k]) return count #utility function to check whether the string is palindrome, Time O(s), Space O(1) def isPalindrome(s): if s is None or len(s)==0: return False n = len(s) for i in range(0, n//2): if s[i] != s[n-i-1]: return False return True s = "lebebe"; print("\npalindromic substrings are (suffix trie): ") print("\ncount is "+ str(countPaliSub(s))); |
Output:
palindromic substrings are (suffix trie):
b
beb
e
ebe
ebebe
l
count is 6
O Notation:
Time complexity: O(s^2)
Space complexity: O(s)
s is input string length
Download FindDistinctPalidromicSubstrings.java
Download FindDistinctPalidromicSubstrings.js
Download FindDistinctPalidromicSubstrings.py
Find distinct palindromic substrings (YouTube)
