title: Left factoring using Python
body: <p>Is there any predefined function in Python to identify the common prefixes on the right side of a production rule?</p>
  
  <p>For example, I need to turn this sort of data structure:</p>
  
  <pre><code>['abc', 'ab', 'd', 'dc']
  </code></pre>
  
  <p>into a dictionary of prefix-to-corresponding suffixes pairs. So my output for this example should look something like this:</p>
  
  <pre><code>{'ab': set(['c', '']), 'd': set(['c', ''])}  # ab is a common prefix and d is a common prefix
  </code></pre>
  
  <p>In more general terms, I need to convert this sort of input:</p>
  
  <pre><code>S -&gt; abc|ab|d|dc
  </code></pre>
  
  <p>into this sort of output:</p>
  
  <pre><code>S -&gt; abA|dA  # prefixes ab and d followed by A
  A -&gt; c|NULL  # where A is either c or an equivalent of None
  </code></pre>
  
  <p>I want to use this output to perform left factoring of a grammar.</p>