0
$\begingroup$

I have written a regex engine and it can match whole strings to a pattern without a problem, i.e.: match(E, w) and it returns true or false if the string $w$ matches the expression $E$ or not. But I was thinking of how to extend the matching function to find substrings in a string that match an expression. The obvious solution is the one I came up with - go through all substrings of the given string and test them against the expression. This is obviously pretty slow since the number of substrings for a string $w$ will be $\frac{|w|(|w| + 1)}{2}$ and even though the matching function has $O(n)$ complexity the extended matching function will be $O(n^3)$. I tried googling around but no actual algorithm describing how this kind of thing would work popped up. So I am asking here...

P.S. I also thought of a way to determine lower and upper bounds for the length of words in the language that a given expression describes but that would only marginally improve the algorithm even if you don't use the star operator.

$\endgroup$
2
  • $\begingroup$ It depends on your engine. I know of a method that transfers the expresssion into a nondeterministic finite state automaton and while reading the string keeps a set of states that can be reached from the initial state. You can feed the engine another copy of the initial state for each next letter from the string. For each state reached you keep a set of positions in the string where the search started. $\endgroup$ Commented Jun 26, 2022 at 16:32
  • $\begingroup$ @HendrikJan I do use an NFA and not a DFA for the RE compilation if that's what you meant. Could you elaborate on your method or link some source explaining it? $\endgroup$
    – Moxy
    Commented Jun 26, 2022 at 16:49

1 Answer 1

0
$\begingroup$

One approach is to match against the regexp .* E .*, then figure out how it matches. Whether you can figure out how that matched depends on the algorithm you are using to implement match. This will look for one substring that matches, not all of them.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.