title: efficiently finding overlapping segments from a set of lists
body: <p>Suppose I have the following lists:</p>
  
  <p><code>[1, 2, 3, 20, 23, 24, 25, 32, 31, 30, 29]
  [1, 2, 3, 20, 23, 28, 29]
  [1, 2, 3, 20, 21, 22]
  [1, 2, 3, 14, 15, 16]
  [16, 17, 18]
  [16, 17, 18, 19, 20]</code></p>
  
  <p>Order matters here. These are the nodes resulting from a depth-first search in a weighted graph. What I want to do is break down the lists into unique paths (where a path has at least 2 elements). So, the above lists would return the following:</p>
  
  <p><code>[1, 2, 3]
  [20, 23]
  [24, 25, 32, 31, 30, 29]
  [28, 29]
  [20, 21, 22]
  [14, 15, 16]
  [16, 17, 18]
  [19, 20]</code></p>
  
  <p>The general idea I have right now is this:</p>
  
  <ol>
  <li><p>Look through all pairs of lists to create a set of lists of overlapping segments <em>at the beginning of the lists</em>. For example, in the above example, this would be the output:<br>
  <code>[1, 2, 3, 20, 23]
  [1, 2, 3, 20]
  [1, 2, 3]
  [16, 17, 18]</code></p></li>
  <li><p>The next output would be this:<br>
  <code>[1, 2, 3]
  [16, 17, 18]</code></p></li>
  <li><p>Once I have the lists from step 2, I look through each input list and chop off the front if it matches one of the lists from step 2. The new lists look like this:<br>
  <code>[20, 23, 24, 25, 32, 31, 30, 29]
  [20, 23, 28, 29]
  [20, 21, 22]
  [14, 15, 16]
  [19, 20]</code></p></li>
  <li><p>I then go back and apply step 1 to the truncated lists from step 3. When step 1 doesn't output any overlapping lists, I'm done.</p></li>
  </ol>
  
  <p>Step 2 is the tricky part here. What's silly is it's actually equivalent to solving the original problem, although on smaller lists.</p>
  
  <p>What's the most efficient way to solve this problem? Looking at all pairs obviously requires O(N^2) time, and step 2 seems wasteful since I need to run the same procedure to solve these smaller lists. I'm trying to figure out if there's a smarter way to do this, and I'm stuck.</p>