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

Pour être complet, difflib dans la bibliothèque standard fournit de nombreux utilitaires de comparaison de séquences. Par exemple find_longest_match qui trouve la plus longue sous-chaîne commune lorsqu'elle est utilisée sur des chaînes de caractères. Exemple d'utilisation :

from difflib import SequenceMatcher

string1 = "apple pie available"
string2 = "come have some apple pies"

match = SequenceMatcher(None, string1, string2).find_longest_match()

print(match)  # -> Match(a=0, b=15, size=9)
print(string1[match.a:match.a + match.size])  # -> apple pie
print(string2[match.b:match.b + match.size])  # -> apple pie

Si vous utilisez une version antérieure à 3.9, vous devez appeler find_longest_match() avec les arguments suivants :

SequenceMatcher(None, string1, string2).find_longest_match(0, len(string1), 0, len(string2))

Answer 2

On peut également envisager os.path.commonprefix qui fonctionne sur les caractères et peut donc être utilisé pour n'importe quelle chaîne de caractères.

import os
common = os.path.commonprefix(['apple pie available', 'apple pies'])
assert common == 'apple pie'

Comme le nom de la fonction l'indique, celle-ci ne prend en compte que le préfixe commun de deux chaînes de caractères.

Answer 3

def common_start(sa, sb):
    """ returns the longest common substring from the beginning of sa and sb """
    def _iter():
        for a, b in zip(sa, sb):
            if a == b:
                yield a
            else:
                return

    return ''.join(_iter())

>>> common_start("apple pie available", "apple pies")
'apple pie'

---

Ou d'une manière un peu plus étrange :

def stop_iter():
    """An easy way to break out of a generator"""
    raise StopIteration

def common_start(sa, sb):
    return ''.join(a if a == b else stop_iter() for a, b in zip(sa, sb))

Ce qui pourrait être plus lisible comme

def terminating(cond):
    """An easy way to break out of a generator"""
    if cond:
        return True
    raise StopIteration

def common_start(sa, sb):
    return ''.join(a for a, b in zip(sa, sb) if terminating(a == b))

Answer 4

C'est le problème de la plus longue sous-chaîne commune. Je présente ici une solution simple, facile à comprendre mais inefficace. Il faudra beaucoup de temps pour produire un résultat correct pour les grandes chaînes de caractères, car la complexité de cet algorithme est O(N^2).

def longestSubstringFinder(string1, string2):
    answer = ""
    len1, len2 = len(string1), len(string2)
    for i in range(len1):
        match = ""
        for j in range(len2):
            if (i + j < len1 and string1[i + j] == string2[j]):
                match += string2[j]
            else:
                if (len(match) > len(answer)): answer = match
                match = ""
    return answer

print(longestSubstringFinder("apple pie available", "apple pies"))
print(longestSubstringFinder("apples", "appleses"))
print(longestSubstringFinder("bapples", "cappleses"))

Sortie

apple pie
apples
apples

Answer 5

Corriger les bugs avec la réponse du premier :

def longestSubstringFinder(string1, string2):
    answer = ""
    len1, len2 = len(string1), len(string2)
    for i in range(len1):
        for j in range(len2):
            lcs_temp = 0
            match = ''
            while ((i+lcs_temp < len1) and (j+lcs_temp<len2) and string1[i+lcs_temp] == string2[j+lcs_temp]):
                match += string2[j+lcs_temp]
                lcs_temp += 1
            if len(match) > len(answer):
                answer = match
    return answer

print(longestSubstringFinder("dd apple pie available", "apple pies"))
print(longestSubstringFinder("cov_basic_as_cov_x_gt_y_rna_genes_w1000000", "cov_rna15pcs_as_cov_x_gt_y_rna_genes_w1000000")
print(longestSubstringFinder("bapples", "cappleses"))
print(longestSubstringFinder("apples", "apples"))