CODEWITHSUNDEEP
algorithmsearchdata-structuressuffix-tree
xxx222
xxx222

Reputation: 3244

How can I find such string in linear time using the suffix tree?

Given a string s of length n, find the longest string t that occurs both forwards and backwards in s. e.g, s = yabcxqcbaz, then return t = abc or t = cba

I am considering using the generalized suffix tree but I think it would take me O(n^2) time.

i = 0 # Initialize the position on the S
j = 0 # Initialize the position on the Sr
n = len(S) # n is the length of the string
maxLengthPos = (0, 0) # Record the maximum length of such substring found so far and its position

# Iterate through every 
for i in range(n):
    for j in range(n):
        maxL, pos = maxLengthPos
        l = LCE(i, j) # The longest common extension which take O(1) time
        if l > maxL:
            maxLength = (l, i)

Can I implement it in O(n) time?

Upvotes: 0

Views: 346

Answers (1)

Niklas B.
Niklas B.

Reputation: 95308

You are looking for the longest common substring of s and its reverse. This can indeed be solved using the generalized suffix array or suffix tree of s and reverse(s), in linear time.

There's a conceptionally simpler approach using the suffix automaton of s though. A suffix automaton is a finite automaton that matches exactly the suffixes of a string, and it can be built in linear time. You can find an implementation in C++ in my Github repository. Now you just feed the second string (in this case reverse(s)) into the automaton and record the longest match, which corresponds to the LCS of the two strings.

Upvotes: 1

Related Questions