title: Python regex catastrophic backtracking
body: <p>I am searching an XML file generated from Ms word for some phrases. The thing is that any phrase can be interrupted with some XML tags, that can come between words, or even inside words, as you can see in the example:</p>
  
  <blockquote>
    <p><code>&lt;/w:rPr&gt;&lt;w:t&gt; To i&lt;/w:t&gt;&lt;/w:r&gt;&lt;w:r wsp:rsidRPr="00EC3076"&gt;&lt;w:rPr&gt;&lt;w:sz w:val="17"/&gt;&lt;w:lang w:fareast="JA"/&gt;&lt;/w:rPr&gt;&lt;w:t&gt;ncrease knowledge of and acquired skills for implementing social policies with a view to strengthening the capacity of developing countries  at the national and community level.&lt;/w:t&gt;&lt;/w:r&gt;&lt;/w:p&gt;</code></p>
  </blockquote>
  
  <p>So my approach to handle this problem was to simply reduce all XML tags into clusters of # characters of the same length, so that when I can find any phrase, the regex would ignore all the XML tags between each two characters.</p>
  
  <p>What I need basically is the span of this phrase within the actual xml document, so I will use this span into later processing with the xml document, I cannot use clones.</p>
  
  <p>This approach works remarkablly, but some phrases cause catastropic backtracking, such as the following example, so I need someone to point out where does the backtracking come from, or suggest a better solution to the problem.</p>
  
  <p>================================</p>
  
  <p>Here is an example:</p>
  
  <p>I have this text where there are some clusters of # characters within it (which I want to keep), and the spaces are also unpredictable, such as the following:</p>
  
  <blockquote>
    Relationship to the #################strategic framework ################## for the period 2014-2015####################: Programme 7, Economic and Social Affairs, subprogramme 3, expected
    
    <p>accomplishment (c)#######</p>
  </blockquote>
  
  <p>In order to match the following phrase:</p>
  
  <blockquote>
    <p>Relationship to the strategic framework for the period 2014-2015:
    programme 7, Economic and Social Affairs, subprogramme 3, expected
    accomplishment (c)</p>
  </blockquote>
  
  <p>I came up with this regex to accommodate the unpredictable # and space characters:</p>
  
  <blockquote>
    <p><code>u'R#*e#*l#*a#*t#*i#*o#*n#*s#*h#*i#*p#*\\s*#*t#*o#*\\s*#*t#*h#*e#*\\s*#*s#*t#*r#*a#*t#*e#*g#*i#*c#*\\s*#*f#*r#*a#*m#*e#*w#*o#*r#*k#*\\s*#*f#*o#*r#*\\s*#*t#*h#*e#*\\s*#*p#*e#*r#*i#*o#*d#*\\s*#*2#*0#*1#*4#*\\-#*2#*0#*1#*5#*:#*\\s*#*p#*r#*o#*g#*r#*a#*m#*m#*e#*\\s*#*7#*\\,#*\\s*#*E#*c#*o#*n#*o#*m#*i#*c#*\\s*#*a#*n#*d#*\\s*#*S#*o#*c#*i#*a#*l#*\\s*#*A#*f#*f#*a#*i#*r#*s#*\\,#*\\s*#*s#*u#*b#*p#*r#*o#*g#*r#*a#*m#*m#*e#*\\s*#*3#*\\,#*\\s*#*e#*x#*p#*e#*c#*t#*e#*d#*\\s*#*a#*c#*c#*o#*m#*p#*l#*i#*s#*h#*m#*e#*n#*t#*\\s*#*\\(#*c#*\\)'</code></p>
  </blockquote>
  
  <p>And it works fine in all the other phrases that I want to match, but this one has a problem leading to some catastrophic backtracking, can anyone spot it?</p>
  
  <p>The original text is separated with xml tags, so to make it simpler for the regex, I replaced the tags with these # clusters, here is the original text:</p>
  
  <blockquote>
    <p><code>&lt;/w:rPr&gt;&lt;w:t&gt;Relationship to the &lt;/w:t&gt;&lt;/w:r&gt;&lt;w:r&gt;&lt;w:rPr&gt;&lt;w:i/&gt;&lt;w:sz w:val="17"/&gt;&lt;w:sz-cs w:val="17"/&gt;&lt;/w:rPr&gt;&lt;w:t&gt;strategic framework &lt;/w:t&gt;&lt;/w:r&gt;&lt;w:r wsp:rsidRPr="00EC3076"&gt;&lt;w:rPr&gt;&lt;w:i/&gt;&lt;w:sz w:val="17"/&gt;&lt;w:sz-cs w:val="17"/&gt;&lt;/w:rPr&gt;&lt;w:t&gt; for the period 2014-2015&lt;/w:t&gt;&lt;/w:r&gt;&lt;w:r wsp:rsidRPr="00EC3076"&gt;&lt;w:rPr&gt;&lt;w:sz w:val="17"/&gt;&lt;w:sz-cs w:val="17"/&gt;&lt;/w:rPr&gt;&lt;w:t&gt;: Programme 7, Economic and Social Affairs, subprogramme 3, expected accomplishment (c)&lt;/w:t&gt;</code></p>
  </blockquote>