Closed lrvideckis closed 8 months ago
idea for test: compare suffix tree to suffix array/lcp
https://codeforces.com/blog/entry/11337
another test idea: compare suffix array to suffix automaton
handle multiple strings, aka "generalized suffix tree"
applications: Suffix Tree Application 1 – Substring Check Suffix Tree Application 2 – Searching All Patterns Suffix Tree Application 3 – Longest Repeated Substring Suffix Tree Application 4 – Build Linear Time Suffix Array Suffix Tree Application 5 – Longest Common Substring Suffix Tree Application 6 – Longest Palindromic Substring
existing implementations:
https://cp-algorithms.com/string/suffix-tree-ukkonen.html https://github.com/kth-competitive-programming/kactl/blob/main/content/strings/SuffixTree.h https://github.com/bqi343/cp-notebook/blob/master/Implementations/content/strings%20(14)/Heavy/SuffixTree.h https://codeforces.com/blog/entry/16780 (code link at end of blog)
PDF explaining how suffix trees work: (it's a pretty nice read actually)
https://www.cs.cmu.edu/afs/cs/project/pscico-guyb/realworld/www/slidesF06/cmuonly/gusfield.pdf