Regex pattern match performance in Java for long string
<p>I have a regex that works great(500 nanoseconds) when a match is found, but takes a lot of time (over 3 secs) when there is no match. I suspect this could be because of backtracking. I tried some options, like converting <code>.*</code> to <code>(.*)?</code> based on some documentation, but it didn't help.</p>

<p>Input: a very long string - 5k chars in some cases.</p>

<p>Regex to match: <code>.*substring1.*substring2.*</code></p>

<p>I am pre-compiling the pattern and re-using the matcher, what else can I try?</p>

<p>Here's my code snippet - I will be calling this method with millions of different input strings, but just a handful of regex patterns.</p>

<pre><code>private static HashMap&lt;String, Pattern&gt; patternMap = new HashMap&lt;String, Pattern&gt;();
private static HashMap&lt;String, Matcher&gt; matcherMap = new HashMap&lt;String, Matcher&gt;();
</code></pre>

<p>Here's my method: </p>

<pre><code>public static Boolean regex_match(String line, String regex) {
    if (regex == null || line == null) {
      return null;
    }
    if (!patternMap.containsKey(regex)) {
      patternMap.put(regex, Pattern.compile(regex));
      matcherMap.put(regex,patternMap.get(regex).matcher(""));
    }
    return matcherMap.get(regex).reset(line).find(0);
 }
</code></pre>