title: How can you parallelize a regex search of one long string?
body: <p>I'm testing the output of a simulation to see if it enters a loop at some point, so I need to know if the output repeats itself. For example, there may be 400 digits, followed by a 400000 digit cycle. The output consists only of digits from 0-9. I have the following regex function that I'm using to match repetitions in a single long string:</p>
  
  <pre><code>def repetitions(s):
      r = re.compile(r"(.+?)\1+")
      for match in r.finditer(s):
          if len(match.group(1)) &gt; 1 and len(match.group(0))/len(match.group(1)) &gt; 4:
              yield (match.group(1), len(match.group(0))/len(match.group(1)))
  </code></pre>
  
  <p>This function works fantastically, but it takes far too long. My most recent test was 4 million digits, and it took 4.5 hours to search. It found no repetitions, so I now need to increase the search space. The code only concerns itself with subsequences that repeat themselves more than 4 times because I'm considering 5 repetitions to give a set that can be checked manually: the simulation will generate subsequences that will repeat hundreds of times. I'm running on a four core machine, and the digits to be checked are generated in real time. How can I increase the speed of the search?</p>