Python - как найти все пересечения двух строк?

Question

Как найти все пересечения (также называемые самыми длинными общими подстроками) двух строк и их положения в обеих строках?

Например, если S1="never" и S2="forever", то результирующее пересечение должно быть ["ever"], а его позиции - [(1,3)]. Если S1="address" и S2="oddness", то приведенные пересечения ["dd","ess"], а их позиции [(1,1),(4,4)].

Самое короткое решение без какой-либо библиотеки является предпочтительным Но любое правильное решение также приветствуется.

Answer 1

Ну, вы говорите, что не можете включить ни одну библиотеку.Тем не менее, стандартный Python difflib содержит функцию, которая делает именно то, что вы ожидаете.Учитывая, что это вопрос Python для интервью, знакомство с difflib может оказаться тем, чего ожидал интервьюер.

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)]

Вы всегда можете игнорировать последний кортеж Match, поскольку он фиктивный (согласно документации).

Answer 2

Это можно сделать в O (n + m), где n и m - длины входных строк.

Псевдокод:

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

См. Longest_common_substring_problem статья в Википедии для более подробной информации.

Answer 3

Вот что я мог придумать:

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]

Проверка некоторых значений:

>>> 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)]

Answer 4

Батарейки в комплекте!

Модуль difflib может вам помочь - вот быстрый и грязный анализ различий:

>>> 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

Answer 5

Я предполагаю, что вы хотите, чтобы подстроки совпадали, только если они имеют одинаковую абсолютную позицию в своих соответствующих строках.Например, «abcd» и «bcde» не будут иметь совпадений, даже если оба содержат «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("_"))

позиции = [1, 2, 4, 5, 6]

подстроки = ['dd', 'ess']

Если вам нужны только подстроки, вы можете поместить их в одну строку:

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("_"))

Answer 6

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' )