Python - comment trouver toutes les intersections de deux chaînes?

Je suppose que vous ne voulez que les sous-chaînes correspondent si elles ont la même position absolue dans leurs chaînes respectives. Par exemple, "abcd" et "bcde" n'auront aucune correspondance, même si les deux contiennent "bcd".

a = "address"
b = "oddness"

#matches[x] is True if a[x] == b[x]
matches = map(lambda x: x[0] == x[1], zip(list(a), list(b)))

positions = filter(lambda x: matches[x], range(len(a)))
substrings = filter(lambda x: x.find("_") == -1 and x != "","".join(map(lambda x: ["_", a[x]][matches[x]], range(len(a)))).split("_"))

Positions = [1, 2, 4, 5, 6]

Substrings = ['dd', 'ess']

Si vous ne voulez que des sous-chaînes, vous pouvez les écraser sur une seule ligne:

filter(lambda x: x.find("_") == -1 and x != "","".join(map(lambda x: ["_", a[x]][map(lambda x: x[0] == x[1], zip(list(a), list(b)))[x]], range(len(a)))).split("_"))

Batteries incluses!

Le module difflib pourrait vous aider - voici un diff côte à côte rapide et sale:

>>> import difflib
>>> list(difflib.ndiff("never","forever"))
['- n', '+ f', '+ o', '+ r', '  e', '  v', '  e', '  r']
>>> diffs = list(difflib.ndiff("never","forever"))
>>> for d in diffs:
...   print {' ': '  ', '-':'', '+':'    '}[d[0]]+d[1:]
...
 n
     f
     o
     r
   e
   v
   e
   r

Cela peut être fait dans O (n + m) où n et m sont des longueurs de chaînes d'entrée.

Le pseudocode est:

function LCSubstr(S[1..m], T[1..n])
    L := array(1..m, 1..n)
    z := 0
    ret := {}
    for i := 1..m
        for j := 1..n
            if S[i] = T[j]
                if i = 1 or j = 1
                    L[i,j] := 1
                else
                    L[i,j] := L[i-1,j-1] + 1
                if L[i,j] > z
                    z := L[i,j]
                    ret := {}
                if L[i,j] = z
                    ret := ret ∪ {S[i-z+1..z]}
    return ret

Consultez l'article Longest_common_substring_problem wikipedia pour plus de détails.

def  IntersectStrings( first,  second):
x = list(first)
#print x
y = list(second)
lst1= []
lst2= []
for i in x:
    if i in y:
        lst1.append(i)
lst2 = sorted(lst1) + []
   # This  above step is an optional if it is required to be sorted      alphabetically use this or else remove it
return ''.join(lst2)

print IntersectStrings('hello','mello' )

Voici ce que je pourrais trouver:

import itertools

def longest_common_substring(s1, s2):
   set1 = set(s1[begin:end] for (begin, end) in
              itertools.combinations(range(len(s1)+1), 2))
   set2 = set(s2[begin:end] for (begin, end) in
              itertools.combinations(range(len(s2)+1), 2))
   common = set1.intersection(set2)
   maximal = [com for com in common
              if sum((s.find(com) for s in common)) == -1 * (len(common)-1)]
   return [(s, s1.index(s), s2.index(s)) for s in maximal]

Vérification de certaines valeurs:

>>> longest_common_substring('address', 'oddness')
[('dd', 1, 1), ('ess', 4, 4)]
>>> longest_common_substring('never', 'forever')
[('ever', 1, 3)]
>>> longest_common_substring('call', 'wall')
[('all', 1, 1)]
>>> longest_common_substring('abcd1234', '1234abcd')
[('abcd', 0, 4), ('1234', 4, 0)]