Regex search with pattern containing (?:.|\s)*? takes increasingly long time

by

The alternation (?:.|\\s)+? is very inefficient, as it involves too much backtracking.

Basically, all variations of this pattern are extremely inefficient: (?:.|\s)*?, (?:.|\n)*?, (?:.|\r\n)*? and there greedy counterparts, too ((?:.|\s)*, (?:.|\n)*, (?:.|\r\n)*). (.|\s)*? is probably the worst of them all.

Why?

The two alternatives, . and \s may match the same text at the same location, the both match regular spaces at least. See this demo taking 3555 steps to complete and .*? demo (with s modifier) taking 1335 steps to complete.

Patterns like (?:.|\n)*? / (?:.|\n)* in Java often cause a Stack Overflow issue, and the main problem here is related to the use of alternation (that already alone causes backtracking) that matches char by char, and then the group is modified with a quantifier of unknown length. Although some regex engines can cope with this and do not throw errors, this type of pattern still causes slowdowns and is not recommended to use (only in ElasticSearch Lucene regex engine the (.|\n) is the only way to match any char).

Solution

If you want to match any characters including whitespace with regex, do it with

[\\s\\S]*?

Or enable singleline mode with (?s) (or Pattern.DOTALL Matcher option) and just use . (e.g. (?s)start(.*?)end).

NOTE: To manipulate HTML, use a dedicated parser, like jsoup. Here is an SO post discussing Java HTML parsers.

More Related Contents:

  1. Search for keywords and replace them with their abbreviations [closed]
  2. Regex to match end-of-sentence markers [closed]
  3. Java regular expression “( *|)”: what does the pipe do? [duplicate]
  4. Want to extract values from text file using regex
  5. Java regex email
  6. Splitting on comma outside quotes
  7. How to use regular expressions to parse HTML in Java?
  8. How to split a string between letters and digits (or between digits and letters)?
  9. How to split a string, but also keep the delimiters?
  10. Whitespace Matching Regex – Java
  11. How can non-ASCII characters be removed from a string?
  12. How to match string within parentheses (nested) in Java?
  13. Regex look-behind without obvious maximum length in Java
  14. Returning overlapping regular expressions
  15. A regex to match a substring that isn’t followed by a certain other substring
  16. Java; String replace (using regular expressions)?
  17. Cancelling a long running regex match?
  18. Regular expression to match a backslash followed by a quote
  19. Why String.replaceAll() in java requires 4 slashes “\\\\” in regex to actually replace “\”?
  20. How to filter string for unwanted characters using regex?
  21. Split a string, at every nth position
  22. replace \n and \r\n with in java
  23. Regex: what is InCombiningDiacriticalMarks?
  24. How to find the exact word using a regex in Java?
  25. Backreferences in lookbehind
  26. Regular Expression to Match String Exactly?
  27. How can I find repeated characters with a regex in Java?
  28. String.replaceAll is considerably slower than doing the job yourself
  29. Remove all occurrences of \ from string
  30. Extract ip addresses from Strings using regex

Leave a Comment