0

For a regex that support only +,?,*,.,|,[..],[^..],^,$,(..), a matcher that lets you match recursion: {<some-regex-name>} with length m, and a string of length n.

(the regex isn't supporting positive/negative look-ahead/behind)

What is the best complexity of the matcher?

Examples:

Bracket Matching:

brackets = (\({brackets}\))*
// brackets can match:
// ((()())())()

Some random "double" recursion:

a = \(({a}|{b})?\)
b = \[{a}(,{b})*\]
// a can match:
// (([(),[(),[()]][(())]]))

Json without whitespaces:

string = "([^\\"]|\\.)"
object = \{ ( {string}:{value}(,{string}:{value})* )? \}
number = [0-9]+(\.[0-9]*)?
list = \[({value}(,{value})*)?]
value = object|string|number|list|true|false
// value can match:
// {"key":false,"ab\"c":[false,12.3,[{}]]}

i have an idea how to implement this with complexity O(m^2*n^3) where n is the size of the string, and m is the size of the regex. i haven't implement this yet, so maybe i have a mistake

Improve this question
12
  • Depends totally on what is inside the regex. You need to add details about the regex itself. Commented Oct 19, 2021 at 10:41
  • @WaisKamal any standard regex patterns. like X+,X*,[...] ect Commented Oct 19, 2021 at 10:43
  • 1
    What does "basic" mean? What does "etc" mean in your list of possible patterns? You won't get any meaningful help until you can describe your problem very precisely. This is all too vague. Note that describing your problem precisely will not only allow you to get answers, but it will help you see more clearly and help yourself solve your problem. Commented Oct 19, 2021 at 11:35
  • 1
    The "match recursion" raises the expressiveness to be coextensive with context-free languages, and I'm guessing your algorithm looks like CYK. If memory serves, there are asymptotically faster algorithms that leverage faster matrix multiplication, but nothing particularly practical. Commented Oct 19, 2021 at 12:29
  • 1
    @ntg there is no connection, he asked for generating every combination of parentheses, i ask for a way to match a recursive regex. the parentheses was only an example to what is my idea. Commented Oct 21, 2021 at 15:00
Related questions
14
Complexity of Regex substitution
90
What is the complexity of regular expression?
82
What's the Time Complexity of Average Regex algorithms?
Load 7 more related questions Show fewer related questions

0

Reset to default

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.