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

Une structure de données Trie fonctionnerait le mieux, mieux que DP. Voici le code.

class TrieNode:
    def __init__(self):
        self.child = [None]*26
        self.endWord = False

class Trie:

    def __init__(self):
        self.root = self.getNewNode()

    def getNewNode(self):
        return TrieNode()

    def insert(self,value):
        root = self.root

        for i,character in enumerate(value):
            index = ord(character) - ord('a')
            if not root.child[index]:
                root.child[index] = self.getNewNode()
            root = root.child[index]

        root.endWord = True

    def search(self,value):
        root = self.root

        for i,character in enumerate(value):
            index = ord(character) - ord('a')
            if not root.child[index]:
                return False
            root = root.child[index]
        return root.endWord

def main(): 

    # Input keys (use only 'a' through 'z' and lower case) 
    keys = ["the","anaswe"] 
    output = ["Not present in trie", 
            "Present in trie"] 

    # Trie object 
    t = Trie() 

    # Construct trie 
    for key in keys: 
        t.insert(key) 

    # Search for different keys 
    print("{} ---- {}".format("the",output[t.search("the")])) 
    print("{} ---- {}".format("these",output[t.search("these")])) 
    print("{} ---- {}".format("their",output[t.search("their")])) 
    print("{} ---- {}".format("thaw",output[t.search("thaw")])) 

if __name__ == '__main__': 
    main() 

Faites-moi savoir en cas de doutes.

Answer 2

Dans le cas où nous avons une liste de mots dont nous avons besoin de trouver toutes les sous-chaînes communes, j'ai vérifié certains des codes ci-dessus et le meilleur est le suivant https://stackoverflow.com/a/42882629/8520109 mais il a quelques bogues, par exemple "histhome y "homéiste . Dans ce cas, nous devrions avoir "hist y Accueil en conséquence. De plus, il diffère si l'ordre des arguments est modifié. Je modifie donc le code pour trouver chaque bloc de sous-chaîne et il en résulte un ensemble de sous-chaînes communes :

main = input().split(" ")    #a string of words separated by space
def longestSubstringFinder(string1, string2):
    '''Find the longest matching word'''
    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

def listCheck(main):
    '''control the input for finding substring in a list of words'''
    string1 = main[0]
    result = []
    for i in range(1, len(main)):
        string2 = main[i]
        res1 = longestSubstringFinder(string1, string2)
        res2 = longestSubstringFinder(string2, string1)
        result.append(res1)
        result.append(res2)
    result.sort()
    return result

first_answer = listCheck(main)

final_answer  = []

for item1 in first_answer:    #to remove some incorrect match
    string1 = item1
    double_check = True
    for item2 in main:
        string2 = item2
        if longestSubstringFinder(string1, string2) != string1:
            double_check = False
    if double_check:
        final_answer.append(string1)

print(set(final_answer))

---

main = 'ABACDAQ BACDAQA ACDAQAW XYZCDAQ' #>>> {'CDAQ'}
main = 'homehist histhome' #>>> {'hist', 'home'}

Answer 3

def LongestSubString(s1,s2):
    if len(s1)<len(s2) :
        s1,s2 = s2,s1  

    maxsub =''
    for i in range(len(s2)):
        for j in range(len(s2),i,-1):
            if s2[i:j] in s1 and j-i>len(maxsub):                
                return  s2[i:j]

Answer 4

Renvoie la première sous-chaîne commune la plus longue :

def compareTwoStrings(string1, string2):
    list1 = list(string1)
    list2 = list(string2)

    match = []
    output = ""
    length = 0

    for i in range(0, len(list1)):

        if list1[i] in list2:
            match.append(list1[i])

            for j in range(i + 1, len(list1)):

                if ''.join(list1[i:j]) in string2:
                    match.append(''.join(list1[i:j]))

                else:
                    continue
        else:
            continue

    for string in match:

        if length < len(list(string)):
            length = len(list(string))
            output = string

        else:
            continue

    return output

Answer 5

Il s'agit du problème de classe appelé "Recherche de la séquence la plus longue". J'ai donné un code simple qui a fonctionné pour moi, aussi mes entrées sont des listes d'une séquence qui peut aussi être une chaîne :

def longest_substring(list1,list2):
    both=[]
    if len(list1)>len(list2):
        small=list2
        big=list1
    else:
        small=list1
        big=list2
    removes=0
    stop=0
    for i in small:
        for j in big:
            if i!=j:
                removes+=1
                if stop==1:
                    break
            elif i==j:
                both.append(i)
                for q in range(removes+1):
                    big.pop(0)
                stop=1
                break
        removes=0
    return both