Längstes gemeinsames Suffix-Präfix

Question

Gibt es einen effizienten Algorithmus, um das längste gemeinsame Suffix und Präfix von zwei verschiedenen Strings zu finden? Die Alphabetgröße ist unbegrenzt.

Formal, lassen Sie String S = wa und T = bw, wobei a, b, w Teilstrings sind. Wie findet man das längste solcher w, gegeben S und T?

Answer 1

Sie können Trie Baum verwenden, es ist sehr nützlich für gemeinsame Suffix