Linear-time suffix parsing for deterministic languages
Mark-Jan Nederhof, Eberhard Bertsch · Journal of the ACM · 1996
We present a linear-time algorithm to decide for any fixed deterministic context-free language L and input string w whether w is a suffix of some string in L . In contrast to a previously published technique, the decision procedure may be extended to produce syntactic structures (parses) without an increase in time complexity. We also show how this algorithm may be applied to pocess incorrect input in linear time.