Simple AlphaNumeric Regex (single spacing) without Catastrophic Backtracking

by

Explanation

Nested group doesn’t automatically causes catastrophic backtracking. In your case, it is because your regex degenerates to the classical example of catastrophic backtracking (a*)*.

Since \s in optional in ^([a-zA-Z0-9'-]+\s?)*$, on input without any spaces but has characters outside the allowed list, the regex simply degenerates to ^([a-zA-Z0-9'-]+)*$.

You can also think in term of expansion of the original regex:

[a-zA-Z0-9'-]+\s?[a-zA-Z0-9'-]+\s?[a-zA-Z0-9'-]+\s?[a-zA-Z0-9'-]+\s?...

Since \s is optional, we can remove it:

[a-zA-Z0-9'-]+[a-zA-Z0-9'-]+[a-zA-Z0-9'-]+[a-zA-Z0-9'-]+...

And we got a series of consecutive [a-zA-Z0-9'-]+, which will try all ways to distribute the characters between themselves and blow up the complexity.

Solution

The standard way to write a regex to match token delimiter token ... delimiter token is token (delimiter token)*. While it is possible to rewrite the regex avoid repeating token, I’d recommend against it, since it is harder to get it right. To avoid repetition , you might want to construct the regex by string concatenation instead.

Following the recipe above:

^[a-zA-Z0-9'-]+(\s[a-zA-Z0-9'-]+)*$

Although you can see repetition in repetition here, there is no catastrophic backtracking, since the regex can only expand to:

[a-zA-Z0-9'-]+\s[a-zA-Z0-9'-]+\s[a-zA-Z0-9'-]+\s[a-zA-Z0-9'-]+...

And \s and [a-zA-Z0-9'-] are mutual exclusive – there is only one way to match any string.

More Related Contents:

  1. Fixing Catastrophic Backtracking in Regular Expression
  2. Reg-ex to validate a sting with digits only but all Zeros are not allowed [closed]
  3. Why doesn’t [01-12] range work as expected?
  4. Regular expression for a string containing one word but not another
  5. How do I use regex in a SQLite query?
  6. Regular expression to limit number of characters to 10
  7. MongoDB Regex Search on Integer Value
  8. When is \G useful application in a regex?
  9. Regex: Determine if two regular expressions could match for the same input?
  10. Regular expression for letters, numbers and – _
  11. How to replace all strings to numbers contained in each string in Notepad++?
  12. Use a function in Powershell replace
  13. Why is this regex using lookbehinds invalid in R?
  14. Using positive-lookahead (?=regex) with re2
  15. Regular expression limit string size
  16. JavaScript: split doesn’t work in IE?
  17. Does lookaround affect which languages can be matched by regular expressions?
  18. Overlapping matches in R
  19. How to execute a Bash command only if a Docker container with a given name does not exist?
  20. How do I check if a filename matches a wildcard pattern
  21. Regexp that matches valid regexps
  22. Implement auto-complete feature using MongoDB search
  23. What’s the regex to match anything except a double quote not preceded by a backslash?
  24. How to order regular expression alternatives to get longest match?
  25. Flutter – Regex in TextFormField
  26. How to do a non-greedy match in grep?
  27. Understanding positive and negative lookaheads
  28. Rename files using regular expression in linux
  29. How to extract domain name from url?
  30. Whats the difference between sed -E and sed -e

Leave a Comment