Comment trouver toutes les intersections (également appelées les sous-chaînes communes les plus longues) de deux chaînes et leurs positions dans les deux chaînes?

Par exemple, si S1="never" et S2="forever", l'intersection résultante doit être ["ever"] et ses positions sont [(1,3)]. Si S1="address" et S2="oddness", les intersections résultantes sont ["dd","ess"] et leurs positions sont [(1,1),(4,4)].

La solution la plus courte sans inclure de bibliothèque est préférable. Mais toute solution correcte est également la bienvenue.

6
psihodelia 27 sept. 2011 à 19:43

6 réponses

Meilleure réponse

Eh bien, vous dites que vous ne pouvez inclure aucune bibliothèque. Cependant, le difflib standard de Python contient une fonction qui fait exactement ce que vous attendez. Étant donné qu'il s'agit d'une question d'entrevue Python, la familiarité avec difflib pourrait être ce à quoi l'intervieweur s'attendait.

In [31]: import difflib

In [32]: difflib.SequenceMatcher(None, "never", "forever").get_matching_blocks()
Out[32]: [Match(a=1, b=3, size=4), Match(a=5, b=7, size=0)]


In [33]: difflib.SequenceMatcher(None, "address", "oddness").get_matching_blocks()
Out[33]: [Match(a=1, b=1, size=2), Match(a=4, b=4, size=3), Match(a=7, b=7, size=0)]

Vous pouvez toujours ignorer le dernier tuple Match, car il est factice (selon la documentation).

12
Michał Bentkowski 28 sept. 2011 à 06:24

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("_"))
1
Kevin 27 sept. 2011 à 16:11

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
4
PaulMcG 27 sept. 2011 à 18:37

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.

7
Michał Šrajer 27 sept. 2011 à 19:06
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' )
0
Sandeep K V 15 févr. 2016 à 02:22

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)]
5
jterrace 27 sept. 2011 à 16:54