What is a time complexity for finding the longest palindromic substring in a string by using the generalized suffix tree?

Category: QuestionsWhat is a time complexity for finding the longest palindromic substring in a string by using the generalized suffix tree?
Editor">Editor Staff asked 1 month ago

What is a time complexity for finding the longest palindromic substring in a string by using the generalized suffix tree?
 
(a) Linear Time
 
(b) Exponential Time
 
(c) Logarithmic Time
 
(d) Cubic Time
 
The above asked question is from Suffix tree in section Trie of Data Structures & Algorithms I
 
I got this question in an online interview.

1 Answers
Editor">Editor Staff answered 1 month ago

Right option is (a) Linear Time
 
The explanation is: Palindrome is a string that is same when reading forward as well as backward. The time complexity for finding the longest palindromic substring in a string by using generalized suffix tree is linear time.