Incremental Regular Expressions
Eugene Kirpichov (via Hacker News):
In this article we further develop Piponi’s approach, which employs a number of beautiful algorithmic techniques from the world of functional programming, to build a Java library for incremental regular expression matching. This is also an interesting investigation into how the functional approach blends together with an imperative language.
[…]
“Incremental” means “match result is efficiently maintained under certain operations”, where the operations include concatenating two strings and splitting a string in part around an index. Obviously, these two operations form a basis for all kinds of rearrangements, such as inserting or deleting a word from the middle of a string, or appending characters to its back or front, etc.
