title: Find simplest regular expression matching all given strings
body: <p>Is there an algorithm that can produce a regular expression (maybe limited to a simplified grammar) from a set of strings such that the evaluation of all possible strings that match the regular expression reproduces the initial set of strings?</p>
  
  <p>It is probably unrealistic to find such a algorithm for grammars of regular expressions with very "complicated" syntax (including arbitrary repetitions, assertions etc.), so let's start with a simplified one which only allows for an <code>OR</code> of substrings:</p>
  
  <p><code>foo(a|b|cd)bar</code> should match <code>fooabar</code>, <code>foobbar</code> and <code>foocdbar</code>.</p>
  
  <h2>Examples</h2>
  
  <p>Given the set of strings <code>h_q1_a</code>, <code>h_q1_b</code>, <code>h_q1_c</code>, <code>h_p2_a</code>, <code>h_p2_b</code>, <code>h_p2_c</code>, the desired output of the algorithm would be <code>h_(q1|p2)_(a|b|c)</code>.</p>
  
  <p>Given the set of strings <code>h_q1_a</code>, <code>h_q1_b</code>, <code>h_p2_a</code>, the desired output of the algorithm would be <code>h_(q1_(a|b)|p2_a)</code>. <em>Note that <code>h_(q1|p2)_(a|b)</code> would</em> not <em>be correct because that expand to 4 strings, including <code>h_p2_b</code>, which was not in the original set of strings.</em></p>
  
  <h2>Use case</h2>
  
  <p>I have a long list of labels which were all produced by putting together substrings. Instead of printing the vast list of strings, I would like to have a compact output indicating what labels are in the list. As the full list has been produced programmatically (using a finite set of pre- and suffixes) I expect the compact notation to be (potentially) much shorter than the initial list. </p>
  
  <p>(The (simplified) regex should be as short as possible, although I am more interested in a practical solution than the best. The trivial answer is of course to just concatenate all strings like A|B|C|D|... which is, however, not helpful.)</p>