Real-time pattern matching and quasi-real-time construction of suffix trees (preliminary version)
S. Rao Kosaraju · 1994
We design simple real-time algorithms for the following problems for any text string T = tltz...tn and pattern string P = plpz...pm: (a) given T#P as input, test whether Pfi is a substring of T, and (b) given T#P as input, test whether P is a substring of T.Even though these results were claimed in a voluminous paper by Slisenko, the design of a convincing and underst anrlable solution is a well-known open problem.Our algorithm is based on a novel top-down suffix tree construction algorithm.This algorithm does not construct the suffix tree in real-time; but. it constructs enough of the suffix tree in real-time so that it can respond to pattern match queries in real-time.1