USACO: PROB Calf Flac

[A.J]

I guess that does make more sense.

[saltpro15]

I suppose using a trie wouldn't work? Just spitballing ideas at this point, I've tried pretty much every obvious approach I can think of.

[bbi5291]

A prefix trie won't help you. A suffix trie takes O(N^2) time and O(N^2) space. With some path compression and leet hax you can reduce both of those requirements to linear. Congratulations, you have just constructed a suffix tree!

[A.J]

bbi5291 wrote:

With some path compression and leet hax you can reduce both of those requirements to linear.

I don't quite see how you can ever possibly get intimidated by me when you are talking about reducing the time and space required for a suffix trie to linear. I would be really impressed if you can present a program that performs in linear time.

[bbi5291]

Hold on a minute. You used Ukkonen's algorithm, and your solution isn't linear time? Ukkonen's algorithm was hailed as the first online linear-time suffix tree construction algorithm. Is it possible that what you built is actually a suffix trie?
btw, there is an "easy" linear-time construction - you use the linear-time divide-and-conquer suffix array construction described in Simple Linear Work Suffix Array Construction by J. Karkkainen, then the linear-time suffix-array-to-lcp-array algorithm described in Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications (T. Kasai, 2001), and finally you put these together to obtain the suffix tree (exercise for the reader).

[A.J]

Alas, I am trying to reconstruct my memory of Ukkonen's algorithm...

How do you know this much, Brian?

[bbi5291]

I don't know all that from memory, of course. I have various bookmarks to stuff like this.
There are some problems on SPOJ that are trivial if you can construct a suffix tree in linear time, so Ivan Katanic and I teamed up to find some info on suffix tree construction. That's how I found out all of this.
btw, here's a partial list (note: many of these have more elegant solutions):
BEADS
BWHEELER
DISUBSTR
LCS
LCS2
MINMOVE
PALIM
SUBST1
TWICE
WPUZZLES
BWHEELER and DISUBSTR are passable with quadratic time/space too, though.

[riveryu]

Can someone explain how LCS would connect to the Calf Flac problem? I'll read what LCS is right now... Pretend I don't know anything.

[CodeMonkey2000]

If you have 2 strings, the LCS algorithm can be used to figure out the largest common sub sequence. For example suppose you have the strings: ABCFG and ABTFG, then the longest common sub-sequence is of length 4 (the largest sequence in both is ABFG).

In this problem it is useful because you are looking for the largest common sub sequence between a string and the reversed version of the string. Although for palindromes, you need to change the the implementation of the algorithm a bit.