Trouver la sous-chaîne commune entre deux chaînes de caractères

Question

J'aimerais comparer 2 cordes et garder la correspondance, en séparant là où la comparaison échoue.

Donc si j'ai 2 cordes -

string1 = apples
string2 = appleses

answer = apples

Autre exemple, la chaîne de caractères peut comporter plus d'un mot.

string1 = apple pie available
string2 = apple pies

answer = apple pie

Je suis sûr qu'il existe un moyen simple en Python de faire cela, mais je n'arrive pas à le faire. Toute aide et explication sont les bienvenues.

Answer 1

**Return the comman longest substring** 
def longestSubString(str1, str2):
    longestString = ""
    maxLength = 0
    for i in range(0, len(str1)):
        if str1[i] in str2:
            for j in range(i + 1, len(str1)):
                if str1[i:j] in str2:
                    if(len(str1[i:j]) > maxLength):
                        maxLength = len(str1[i:j])
                        longestString =  str1[i:j]
return longestString

Answer 2

Comme si cette question n'avait pas assez de réponses, voici une autre option :

from collections import defaultdict
def LongestCommonSubstring(string1, string2):
    match = ""
    matches = defaultdict(list)
    str1, str2 = sorted([string1, string2], key=lambda x: len(x))

    for i in range(len(str1)):
        for k in range(i, len(str1)):
            cur = match + str1[k]
            if cur in str2:
                match = cur
            else:
                match = ""

            if match:
                matches[len(match)].append(match)

    if not matches:
        return ""

    longest_match = max(matches.keys())

    return matches[longest_match][0]

Quelques exemples de cas :

LongestCommonSubstring("whose car?", "this is my car")
> ' car'
LongestCommonSubstring("apple pies", "apple? forget apple pie!")
> 'apple pie'

Answer 3

Ce n'est pas la façon la plus efficace de procéder, mais c'est ce que j'ai trouvé et ça marche. Si quelqu'un peut l'améliorer, qu'il le fasse. Ce qu'il fait, c'est qu'il crée une matrice et met 1 là où les caractères correspondent. Ensuite, il parcourt la matrice pour trouver la plus longue diagonale de 1, en gardant la trace de son début et de sa fin. Ensuite, il retourne la sous-chaîne de la chaîne d'entrée avec les positions de début et de fin comme arguments.

Remarque : cette méthode ne trouve qu'une seule sous-chaîne commune la plus longue. S'il y en a plus d'une, vous pouvez créer un tableau pour stocker les résultats et les renvoyer. De plus, il est sensible à la casse, donc (Apple pie, apple pie) renverra pple pie.

def longestSubstringFinder(str1, str2):
answer = ""

if len(str1) == len(str2):
    if str1==str2:
        return str1
    else:
        longer=str1
        shorter=str2
elif (len(str1) == 0 or len(str2) == 0):
    return ""
elif len(str1)>len(str2):
    longer=str1
    shorter=str2
else:
    longer=str2
    shorter=str1

matrix = numpy.zeros((len(shorter), len(longer)))

for i in range(len(shorter)):
    for j in range(len(longer)):               
        if shorter[i]== longer[j]:
            matrix[i][j]=1

longest=0

start=[-1,-1]
end=[-1,-1]    
for i in range(len(shorter)-1, -1, -1):
    for j in range(len(longer)):
        count=0
        begin = [i,j]
        while matrix[i][j]==1:

            finish=[i,j]
            count=count+1 
            if j==len(longer)-1 or i==len(shorter)-1:
                break
            else:
                j=j+1
                i=i+1

        i = i-count
        if count>longest:
            longest=count
            start=begin
            end=finish
            break

answer=shorter[int(start[0]): int(end[0])+1]
return answer

Answer 4

D'abord un aide fonction adaptée de la recette itertools par paire pour produire des sous-chaînes.

import itertools
def n_wise(iterable, n = 2):
    '''n = 2 -> (s0,s1), (s1,s2), (s2, s3), ...

    n = 3 -> (s0,s1, s2), (s1,s2, s3), (s2, s3, s4), ...'''
    a = itertools.tee(iterable, n)
    for x, thing in enumerate(a[1:]):
        for _ in range(x+1):
            next(thing, None)
    return zip(*a)

Ensuite, une fonction qui itère sur les sous-chaînes, la plus longue en premier, et teste l'appartenance. (l'efficacité n'est pas prise en compte)

def foo(s1, s2):
    '''Finds the longest matching substring
    '''
    # the longest matching substring can only be as long as the shortest string
    #which string is shortest?
    shortest, longest = sorted([s1, s2], key = len)
    #iterate over substrings, longest substrings first
    for n in range(len(shortest)+1, 2, -1):
        for sub in n_wise(shortest, n):
            sub = ''.join(sub)
            if sub in longest:
                #return the first one found, it should be the longest
                return sub

s = "fdomainster"
t = "exdomainid"
print(foo(s,t))

---

>>> 
domain
>>>

Answer 5

def LongestSubString(s1,s2):
    left = 0
    right =len(s2)
    while(left<right):
        if(s2[left] not in s1):
            left = left+1
        else:
            if(s2[left:right] not in s1):
                right = right - 1
            else:
                return(s2[left:right])

s1 = "pineapple"
s2 = "applc"
print(LongestSubString(s1,s2))