Finding multiple repetitions of smaller lists in a large cumulative list
<p>I have a large list of strings, for eg:</p>

<pre><code>full_log = ['AB21','BG54','HG89','NS72','Error','CF54','SD62','KK02','FE34']
</code></pre>

<p>and multiple small list of strings, for eg:</p>

<pre><code>tc1 = ['HG89','NS72']
tc2 = ['AB21','BG54']
tc3 = ['KK02','FE34']
tc4 = ['CF54','SD62']
</code></pre>

<p>I want to find each of this smaller lists in the larger list maintaining the sequence, so that the output would be something like:</p>

<pre><code>tc2-tc1-Er-tc4-tc3
</code></pre>

<p>I want to know if there is any straight forward, pythonic way of dealing with this situation.</p>

<p>In case all your short lists are equal length you could just create a <code>dict</code> where key is <code>tuple</code> of strings and value is one of the labels. The you could go through <code>full_log</code>, take a block with suitable length and see if that can be found from <code>dict</code>.</p>

<p>In case the short lists are different lengths the above approach won't work since the block length to take from <code>full_log</code> is not constant. In that case one possible solution is to add items from short lists to a tree structure where the leaf node is a label. Then for every index in <code>full_log</code> see if you can find a path from tree. If path is found jump it's length forward, otherwise try from next index:</p>

<pre><code>from collections import defaultdict
from itertools import islice

full_log = ['AB21','BG54','HG89','NS72','Error','CF54','SD62','KK02','FE34']

# Construct a tree
dd = lambda: defaultdict(dd)
labels = defaultdict(dd)
labels['HG89']['NS72'] = 'tc1'
labels['AB21']['BG54'] = 'tc2'
labels['KK02']['FE34'] = 'tc3'
labels['CF54']['SD62'] = 'tc4'

# Find label, return tuple (label, length) or (None, 1)
def find_label(it):
    length = 0
    node = labels
    while node and isinstance(node, dict):
        node = node.get(next(it, None))
        length += 1

    return node, (length if node else 1)

i = 0
result = []
while i &lt; len(full_log):
    label, length = find_label(islice(full_log, i, None))
    result.append(label if label else full_log[i])
    i += length

print result # ['tc2', 'tc1', 'Error', 'tc4', 'tc3']
</code></pre>

<p>The tree used above is kind of <a href="https://en.wikipedia.org/wiki/Trie" rel="nofollow">trie</a> with an exception that nodes can either contain children or a value (label).</p>

python list