title: Extracting static strings from a regular expression
body: <p>I'm trying to efficiently extract static strings (strings that <strong>MUST</strong> be matched for a given regular expression to match). I've been able to do it in the simplest cases but I'm trying to discover a more robust solution.</p>
  
  <hr>
  
  <p>Given a regex such as the one below</p>
  
  <pre><code>"fox jump(ed|ing|s)"
  </code></pre>
  
  <p>would give us</p>
  
  <pre><code>"fox,jumped,jumping,jumps"
  </code></pre>
  
  <hr>
  
  <p>Another example is</p>
  
  <pre><code>"fox jump(ed|ing|s)?"
  </code></pre>
  
  <p>which would give us</p>
  
  <pre><code>"fox,jump"
  </code></pre>
  
  <p>because of the optional operator</p>
  
  <hr>
  
  <p>The algorithm I have is overly simple for now. It will start from the end of the regex and removes groups or a single character followed by these operators "* ?" as well as "explode" grouped OR operators "(|)". This has worked quite well but doesn't take into consideration the full syntax of a regex. You can think of it as kind of a minimal set generating process for a regex (the minimal set of strings that the regex can "generate/must match").</p>
  
  <p><em><strong>WHY?</em></strong>
  I'm trying to match a bunch of text against a large set of regexes. If I can get a list of "keywords" for these regexes that is "required" I can do a quick text search for that keyword to filter the regexes I care about (ignore the ones I am guaranteed to not match or even skip that text entirely effectively not running any regexes on the text because we are guarenteed to not have a match within our set of regexes). I can organize this set of keywords in an efficient data structure (Binary Search/Trie/Aho-Corasick) to filter the set of regexes before I even try to run the text through the Finite Automata. There are extremely fast string matching algorithms that I can run as a filtering stage before I attempt to run a regular expression. I've been able to increase throughput many folds doing this simple process.</p>