3 ms·

can we get the "too stupid, didn't understand" version?

• deleted 14y ago
  [deleted]
• RyanZAG 14y ago
  This is a Java library that handles regular expressions in a new way. The regular expression can be run on a large character string and it supports changes to the string without having to recompute the entire expression. The supported changes to the string are concatenating two strings, or cutting a string into parts. This allows for adding/removing characters from a string. Best use for this (imo) is in doing a regular expression over a large user entered document. As the user types, we can give regular expression updates in real time as we do not need to recompute everything. Limits: "we only have character classes, braces and the operators +, *, ?, |", so only basic expressions.
  • pjscott 14y ago
    Nice explanation. One more thing: this also leads to an algorithm for doing ordinary, non-incremental regular expression matching in O(lg n) time on a parallel machine. It uses a clever method which I think was first discovered on the old Connection Machines by Danny Hillis and Guy Steele: http://cva.stanford.edu/classes/cs99s/papers/hillis-steele-data-parallel-algorithms.pdf http://cva.stanford.edu/classes/cs99s/papers/hillis-steele-d...