Saturday, July 4, 2009

Suffix Trees based Diff Java Applet

Suffix Trees based Diff Java Applet:

See also: my other Suffix Trees posts


Vinicius said...

Illya, your work with suffix trees is being very helpful for me, since my final year project in college is about Ukkonen's algorithm.

I also have coded a Java version of Mark Nelson's implementation (before I found yours), but, although I have understood the algorithm, I'm having a hard time trying to understand why it's O(n).

Ukkonen's original paper is kinda confusing at some points. At page 15, I understand when he says that, excluding the canonize function, each phase takes time proportional to the number of visited states, but when he starting relating this to the depth of consecutive active points, I get lost.

Can you help me with this, maybe linking me to some better explanation?

Thanks again!

hlb said...

I tried the applet with the two following strings:

Only one A is highlighted.
In my understanding, the two A should be highlighted, no ?