Find common subsequence in list

Question

If I have two list such as

list1 = ['cat', 'sat', 'on', 'mat', 'xx', 'yy'] ,
list2 = ['cow', 'sat', 'on', 'carpet', 'xx', 'yy']

I have walk along the lists: when I see two elements that match, start counting. when I see another pair of elements that don't match, stop that counter and start another one.

(sat, sat) I = 1

(on, on) I = 2

(mat, carpet) J = 1

(xx, xx) k = 1

(yy, yy) k = 2

i = 0
for x in list1:
    for y in list2:
        if x == y:
            print (x, y)
            i += 1
        else:
            j = 0
            j += 1
            print (x, y)

Your question is not entirely clear and your code doesn't reflect your intentions. Please explain clearly. Also, why is this tagged nltk? — sshashank124, May 26 '14 at 14:39
`walk along the list`: probably `for item_1, item_2 in zip(list1, list2):` — njzk2, May 26 '14 at 14:44
Could you tell us what the actual output should look like given the input above? — s16h, May 26 '14 at 14:45
possible duplicate of [Longest Common Substring without cutting a word- python](http://stackoverflow.com/questions/22726177/longest-common-substring-without-cutting-a-word-python) — alvas, May 27 '14 at 11:32
The out that should look like (sat, sat), (on,on), (xx, xx), (yy, yy) for matching elements — user3657345, May 27 '14 at 15:55

score 0 · Answer 1 · answered May 26 '14 at 14:49

What about the following :

def doit(list1, list2):
    lastmatch = -1
    lastunmatch = -1
    for i, x in enumerate(zip(list1, list2)):
        if x[0] == x[1]:
            lastmatch = i                
        else:
            lastunmatch = i
        print abs(lastmatch - lastunmatch)

Running : http://ideone.com/xnJWtz

score 0 · Accepted Answer · answered May 26 '14 at 15:01

>>> from collections import defaultdict
>>>
>>> list1 = ['cat', 'sat', 'on', 'mat', 'xx', 'yy']
>>> list2 = ['cow', 'sat', 'on', 'carpet', 'xx', 'yy']
>>>
>>> var_it = iter('IJKLMNOPQRSTUVWXYZ') # variable candidates
>>> counters = defaultdict(int)
>>> c = next(var_it)
>>> for word1, word2 in zip(list1, list2):
...     if word1 == word2:
...         counters[c] += 1
...     else:
...         if counters: # Prevent counting until first match
...             counters[next(var_it)] = 1
...             c = next(var_it)
...
>>> for var in sorted(counters):
...     print('{}: {}'.format(var, counters[var]))
...
I: 2
J: 1
K: 2

Find common subsequence in list

2 Answers2