Suffix Tree Algorithm implemented in Python, might be the most complete version online, even more complete than that demonstrated on stackoverflow.
I underestimated the complication of the algorithm and just wanted to have some fun. A primitive implementation was done in a couple of hours, and the demonstation example on stackoverflow works just fine. Then when I wanted try some more complicated examples, I kept hitting the wall time and time again. It annoyed me, and thus costed me several days to try different situations when constructing a suffix tree.
Finally, the version comes out, I think all the situations explained in the questions and answers have been experienced and covered in the algorithm above before I read the full post.
I also write a blog on explaining the implementation details on my blogger MuTuX with flowcharts and explanation on it.
docs = ['abcabxabcd', 'dedododeeodoeodooedeeododooodoede$', 'ooooooooo', 'mississippi']
for text in docs:
tree, pst = build(text, regularize=True)
Node.draw(tree, pst, ed='#')
The running results:
abcabxabcd
● (0)
|
| ab
----------------● (4->6)
| |
| | xabcd
| ---------------● (5)
| |
| | c
| ---------------● (9->11)
| |
| | abxabcd
| ---------------● (1)
| |
| | d
| ---------------● (10)
|
| c
----------------● (13)
| |
| | abxabcd
| ---------------● (3)
| |
| | d
| ---------------● (14)
|
| b
----------------● (6)
| |
| | xabcd
| ---------------● (7)
| |
| | c
| ---------------● (11->13)
| |
| | abxabcd
| ---------------● (2)
| |
| | d
| ---------------● (12)
|
| xabcd
----------------● (8)
|
| d
----------------● (15)
dedododeeodoeodooedeeododooodoede$
● (0)
|
| e
----------------------------------------● (28)
| |
| | $
| ---------------------------------------● (71)
| |
| | eodo
| ---------------------------------------● (48->37)
| |
| | eodooedeeododooodoede$
| ---------------------------------------● (29)
| |
| | dooodoede$
| ---------------------------------------● (49)
| |
| | d
| ---------------------------------------● (44->19)
| |
| | ododeeodoeodooedeeododooodoede$
| ---------------------------------------● (18)
| |
| | e
| ---------------------------------------● (68->26)
| |
| | eododooodoede$
| ---------------------------------------● (45)
| |
| | $
| ---------------------------------------● (69)
| |
| | odo
| ---------------------------------------● (37->31)
| |
| | eodooedeeododooodoede$
| ---------------------------------------● (30)
| |
| | dooodoede$
| ---------------------------------------● (50)
| |
| | oedeeododooodoede$
| ---------------------------------------● (38)
|
| d
----------------------------------------● (19)
| |
| | e
| ---------------------------------------● (26->28)
| |
| | dododeeodoeodooedeeododooodoede$
| ---------------------------------------● (17)
| |
| | $
| ---------------------------------------● (70)
| |
| | eodo
| ---------------------------------------● (46->48)
| |
| | eodooedeeododooodoede$
| ---------------------------------------● (27)
| |
| | dooodoede$
| ---------------------------------------● (47)
| |
| | o
| ---------------------------------------● (33->35)
| |
| | e
| ---------------------------------------● (64->42)
| |
| | de$
| ---------------------------------------● (65)
| |
| | odooedeeododooodoede$
| ---------------------------------------● (34)
| |
| | d
| ---------------------------------------● (22->24)
| |
| | eeodoeodooedeeododooodoede$
| ---------------------------------------● (23)
| |
| | o
| ---------------------------------------● (53->31)
| |
| | deeodoeodooedeeododooodoede$
| ---------------------------------------● (20)
| |
| | oodoede$
| ---------------------------------------● (54)
| |
| | o
| ---------------------------------------● (57->59)
| |
| | edeeododooodoede$
| ---------------------------------------● (40)
| |
| | odoede$
| ---------------------------------------● (58)
|
| o
----------------------------------------● (35)
| |
| | e
| ---------------------------------------● (42->28)
| |
| | odooedeeododooodoede$
| ---------------------------------------● (36)
| |
| | de
| ---------------------------------------● (66->68)
| |
| | eododooodoede$
| ---------------------------------------● (43)
| |
| | $
| ---------------------------------------● (67)
| |
| | d
| ---------------------------------------● (24->19)
| |
| | eeodoeodooedeeododooodoede$
| ---------------------------------------● (25)
| |
| | o
| ---------------------------------------● (31->33)
| |
| | e
| ---------------------------------------● (62->64)
| |
| | de$
| ---------------------------------------● (63)
| |
| | odooedeeododooodoede$
| ---------------------------------------● (32)
| |
| | d
| ---------------------------------------● (51->22)
| |
| | eeodoeodooedeeododooodoede$
| ---------------------------------------● (21)
| |
| | ooodoede$
| ---------------------------------------● (52)
| |
| | o
| ---------------------------------------● (55->57)
| |
| | edeeododooodoede$
| ---------------------------------------● (39)
| |
| | odoede$
| ---------------------------------------● (56)
| |
| | o
| ---------------------------------------● (59->35)
| |
| | edeeododooodoede$
| ---------------------------------------● (41)
| |
| | doede$
| ---------------------------------------● (61)
| |
| | odoede$
| ---------------------------------------● (60)
|
| $
----------------------------------------● (72)
ooooooooo$
● (0)
|
| o
----------------● (89)
| |
| | $
| ---------------● (90)
| |
| | o
| ---------------● (87->89)
| |
| | $
| ---------------● (88)
| |
| | o
| ---------------● (85->87)
| |
| | $
| ---------------● (86)
| |
| | o
| ---------------● (83->85)
| |
| | $
| ---------------● (84)
| |
| | o
| ---------------● (81->83)
| |
| | $
| ---------------● (82)
| |
| | o
| ---------------● (79->81)
| |
| | $
| ---------------● (80)
| |
| | o
| ---------------● (77->79)
| |
| | $
| ---------------● (78)
| |
| | o
| ---------------● (75->77)
| |
| | $
| ---------------● (76)
| |
| | o$
| ---------------● (74)
|
| $
----------------● (91)
mississippi$
● (0)
|
| i
------------------● (104)
| |
| | ppi$
| -----------------● (105)
| |
| | $
| -----------------● (109)
| |
| | ssi
| -----------------● (98->100)
| |
| | ppi$
| -----------------● (99)
| |
| | ssippi$
| -----------------● (94)
|
| p
------------------● (107)
| |
| | i$
| -----------------● (108)
| |
| | pi$
| -----------------● (106)
|
| s
------------------● (96)
| |
| | i
| -----------------● (102->104)
| |
| | ppi$
| -----------------● (103)
| |
| | ssippi$
| -----------------● (97)
| |
| | si
| -----------------● (100->102)
| |
| | ppi$
| -----------------● (101)
| |
| | ssippi$
| -----------------● (95)
|
| mississippi$
------------------● (93)
|
| $
------------------● (110)
Have fun!