Find all distinct palindromic substrings using suffix trie

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”.

suffix trie substrings

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. 




palindromic substrings are (suffix trie):
count is 6

O Notation:
Time complexity: O(s^2)
Space complexity: O(s)
s is input string length

Download FindDistinctPalidromicSubstrings.js
Find distinct palindromic substrings (YouTube)

Comments are closed