Suchen Sie eine gemeinsame Teilzeichenfolge zwischen zwei Zeichenfolgen

73

Ich möchte 2 Zeichenfolgen vergleichen und die Übereinstimmung beibehalten und dort aufteilen, wo der Vergleich fehlschlägt.

Also wenn ich 2 Saiten habe -

string1 = apples
string2 = appleses

answer = apples

Ein weiteres Beispiel, da die Zeichenfolge mehr als ein Wort enthalten kann.

string1 = apple pie available
string2 = apple pies

answer = apple pie

Ich bin mir sicher, dass es eine einfache Python-Methode gibt, aber ich kann es nicht herausfinden, jede Hilfe und Erklärung wird geschätzt.

Nordseite
quelle
8
Was ist wenn string1 = bapplesund string2 = cappleses?
Ashwini Chaudhary
11
Wenn Sie ein gemeinsames Präfix benötigen : os.path.commonprefix(['apples', 'appleses']) -> 'apples'`
jfs
Schauen Sie sich auch Algorithmus-Implementierungen auf Wikibooks an: en.wikibooks.org/w/index.php?title=Algorithm_Implementation/…
tommy.carstensen
Der Inhalt der Frage entspricht nicht dem Titel. Das beschriebene Problem ist das längste häufige Präfix
heorhi

Antworten:

22

Es heißt Longest Common Substring Problem. Hier präsentiere ich eine einfache, leicht verständliche, aber ineffiziente Lösung. Es wird lange dauern, bis die korrekte Ausgabe für große Zeichenfolgen erfolgt, da die Komplexität dieses Algorithmus O (N ^ 2) ist.

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

Ausgabe

apple pie
apples
apples
thefourtheye
quelle
4
Dieser Algorithmus ist bei bestimmten Eingaben (z. B. "Apfelkuchen ...", "Apfelkuchen") nicht korrekt, funktioniert jedoch, wenn Sie die Parameterposition wechseln. Ich denke, es ist etwas falsch mit der if-Anweisung, wenn Sie vergleicheni+j < len1
REALFREE
Dies funktioniert für das längste Präfix und bricht bei Suffixen ab. ZBx = "cov_basic_as_cov_x_gt_y_rna_genes_w1000000" y = "cov_rna15pcs_as_cov_x_gt_y_rna_genes_w1000000"
Dima Lituiev
8
Es ist völlig falsch. versuchen Sie string1 = "2193588", string2 = "21943588"
Nozar Safari
1
Dies muss Stimmen
verlieren
1
Dies funktioniert nicht, da das Szenario nicht berücksichtigt wird, in dem Sie eine "Neuanpassung" für die zweite Zeichenfolge durchführen müssen. Wenn Sie beispielsweise in "acdaf" gegen "acdacdaf" von "a" der ersten Zeichenfolge ausgehen, stimmt diese bis zum "acda" -Teil der zweiten Zeichenfolge überein und wird dann bei c unterbrochen. Dann egal was du nicht mehr abholen kannst acdaf.
Tamaki Sakura
157

Der Vollständigkeit difflibhalber bietet die Standardbibliothek eine Vielzahl von Dienstprogrammen zum Vergleichen von Sequenzen. Zum Beispiel, find_longest_matchdas die längste gemeinsame Teilzeichenfolge findet, wenn es für Zeichenfolgen verwendet wird. Anwendungsbeispiel:

from difflib import SequenceMatcher

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

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

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
RickardSjogren
quelle
3
Wenn Sie dies für längere Zeichenfolgen verwenden, sollten Sie beim Erstellen der SequenceMatcher-Instanz den kwarg "autojunk" auf "False" setzen.
MLP
1
Ich werde bemerken, dass es in difflib noch ausstehende Fehler gibt, die die Verwendung in realen Szenarien verhindern sollten. Zum Beispiel scheint die bekannte "Heuristik" die Vollständigkeit von Methoden wie "get_matching_blocks" zu beeinträchtigen.
W4t3randWind
2
Warnung: Diese Antwort findet nicht die längste gemeinsame Teilzeichenfolge! Tut trotz seines Namens (und der Dokumentation der Methode) find_longest_match()nicht das, was sein Name impliziert. Die Klassendokumentation für SequenceMatcherweist jedoch darauf hin und sagt : This does not yield minimal edit sequences. In einigen Fällen find_longest_match()wird beispielsweise behauptet, dass es keine Übereinstimmungen in zwei Zeichenfolgen mit einer Länge von 1000 gibt, obwohl es übereinstimmende Teilzeichenfolgen mit einer Länge von> 500 gibt.
Aleksi Torhamo
36
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'

Oder etwas seltsamer:

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

Welches könnte besser lesbar sein als

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))
Eric
quelle
7
Diese Lösung ist derzeit noch nicht vollständig. Es werden nur beide Zeichenfolgen von der nullten Position aus verglichen. Zum Beispiel: >>> common_start ("XXXXXapple pie available", "apple pies") gibt eine leere Zeichenfolge zurück.
Nitin Nain
2
@NitinNain: Das wurde in der ursprünglichen Frage nie geklärt. Aber ja, diese Lösung findet nur den gemeinsamen Beginn der Zeichenfolgen
Eric
1
Funktioniert dies, sobald PEP479 in Kraft ist?
Janus Troelsen
1
Nein - aus diesem Dokument : "Es gibt auch Beispiele für herumschwebende Generatorausdrücke, die auf einer StopIteration beruhen, die durch den Ausdruck, das Ziel oder das Prädikat ausgelöst wird (und nicht durch den Aufruf __next __ (), der in der eigentlichen for-Schleife impliziert ist). "
Eric
1
@Eric noch aus den Python 3.6 Versionshinweisen , Raising the StopIteration exception inside a generator will now generate a DeprecationWarning. Wenn Sie Ihren Code mit ausführen Python3 -W default::DeprecationWarning, DeprecationWarning
lösen
24

Man könnte auch in Betracht ziehen, os.path.commonprefixdass dies mit Zeichen funktioniert und somit für beliebige Zeichenfolgen verwendet werden kann.

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

Wie der Funktionsname angibt, berücksichtigt dies nur das gemeinsame Präfix zweier Zeichenfolgen.

Jonas
quelle
1
Es funktioniert nicht, wenn man Zeichenfolgen wie ['ein Apfelkuchen verfügbar', 'Apfelkuchen'] vergleicht.
GoTop
1
Klare Antwort, es sollte klar sein, was diese Lösung jetzt tut. Die Frage ist in dieser Hinsicht etwas vage. Der Titel schlägt "jede Teilzeichenfolge" vor, Beschreibung und Beispiele geben "allgemeines Präfix" an.
Jonas
@famzah Sie haben einen Link zu der Dokumentation erstellt, die os.commonpathnicht mit der os.commonprefixin der Antwort verwendeten übereinstimmt . Aber wahr, es könnte einige Einschränkungen geben, nur die Dokumentation erwähnt keine.
Jonas
5

Das gleiche wie bei Evo , jedoch mit einer beliebigen Anzahl von zu vergleichenden Zeichenfolgen:

def common_start(*strings):
    """ Returns the longest common substring
        from the beginning of the `strings`
    """
    def _iter():
        for z in zip(*strings):
            if z.count(z[0]) == len(z):  # check all elements in `z` are the same
                yield z[0]
            else:
                return

    return ''.join(_iter())
SergeyR
quelle
4

Beheben Sie Fehler mit der Antwort des Ersten:

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")
user7733798
quelle
2

Versuchen:

import itertools as it
''.join(el[0] for el in it.takewhile(lambda t: t[0] == t[1], zip(string1, string2)))

Es führt den Vergleich von Anfang an beider Zeichenfolgen durch.

Birei
quelle
Ich möchte jetzt, dass Python it.takewhileeine Sprachfunktion erstellt:a for a, b in zip(string1, string2) while a == b
Eric
''.join(el[0] for el in itertools.takewhile(lambda t: t[0] == t[1], zip("ahello", "hello")))gibt zurück "", was falsch zu sein scheint. Das richtige Ergebnis wäre "hello".
Anderson Green
@AndersonGreen: Sie haben Recht, es beantwortet nicht genau die Frage, obwohl seine Beispiele nur den Ausgangspunkt beim ersten Zeichen berücksichtigten und ich auch in meiner Antwort darauf hinwies.
Birei
1
def matchingString(x,y):
    match=''
    for i in range(0,len(x)):
        for j in range(0,len(y)):
            k=1
            # now applying while condition untill we find a substring match and length of substring is less than length of x and y
            while (i+k <= len(x) and j+k <= len(y) and x[i:i+k]==y[j:j+k]):
                if len(match) <= len(x[i:i+k]):
                   match = x[i:i+k]
                k=k+1
    return match  

print matchingString('apple','ale') #le
print matchingString('apple pie available','apple pies') #apple pie     
radhikesh93
quelle
1

Eine Trie-Datenstruktur würde am besten funktionieren, besser als DP. Hier ist der 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() 

Lassen Sie es mich im Zweifelsfall wissen.

Vishwam Pandya
quelle
1

Falls wir eine Liste von Wörtern haben, die wir brauchen, um alle gängigen Teilzeichenfolgen zu finden, überprüfe ich einige der obigen Codes und die beste war https://stackoverflow.com/a/42882629/8520109, aber es gibt einige Fehler, zum Beispiel 'histhome' und "Homehist" . In diesem Fall sollten wir als Ergebnis "hist" und "home" haben . Darüber hinaus unterscheidet es sich, wenn die Reihenfolge der Argumente geändert wird. Also ändere ich den Code, um jeden Teilstring-Block zu finden, und es ergibt sich eine Reihe allgemeiner Teilstrings:

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

rahimz
quelle
0

Gibt den ersten längsten gemeinsamen Teilstring zurück:

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
Modul
quelle
0

Dies ist nicht der effizienteste Weg, aber es ist das, was ich mir einfallen lassen könnte und es funktioniert. Wenn jemand es verbessern kann, bitte tun. Es erstellt eine Matrix und setzt 1, wo die Zeichen übereinstimmen. Dann scannt es die Matrix, um die längste Diagonale von 1s zu finden, und verfolgt, wo sie beginnt und endet. Anschließend wird die Teilzeichenfolge der Eingabezeichenfolge mit den Start- und Endpositionen als Argumente zurückgegeben.

Hinweis: Dies findet nur einen längsten gemeinsamen Teilstring. Wenn es mehr als ein Array gibt, können Sie ein Array erstellen, in dem die Ergebnisse gespeichert werden, und das zurückgeben. Außerdem wird zwischen Groß- und Kleinschreibung unterschieden, sodass (Apfelkuchen, Apfelkuchen) Pple Pie zurückgibt.

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
Rali Tsanova
quelle
0
**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
Jagat Singh
quelle
0

Dies ist das Klassenzimmerproblem, das als "Längster Sequenzfinder" bezeichnet wird. Ich habe einen einfachen Code angegeben, der für mich funktioniert hat. Außerdem sind meine Eingaben Listen einer Sequenz, die auch eine Zeichenfolge sein kann:

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
Bantu Manjunath
quelle
0

Dieses Skript fordert Sie zur Mindestlänge der gemeinsamen Teilzeichenfolge auf und gibt alle gemeinsamen Teilzeichenfolgen in zwei Zeichenfolgen an. Außerdem werden kürzere Teilzeichenfolgen eliminiert, die bereits längere Teilzeichenfolgen enthalten.

def common_substrings(str1,str2):
    len1,len2=len(str1),len(str2)

    if len1 > len2:
        str1,str2=str2,str1
        len1,len2=len2,len1

    min_com = int(input('Please enter the minumum common substring length:'))
    
    cs_array=[]
    for i in range(len1,min_com-1,-1):
        for k in range(len1-i+1):
            if (str1[k:i+k] in str2):
                flag=1
                for m in range(len(cs_array)):
                    if str1[k:i+k] in cs_array[m]:
                    #print(str1[k:i+k])
                        flag=0
                        break
                if flag==1:
                    cs_array.append(str1[k:i+k])
    if len(cs_array):
        print(cs_array)
    else:
        print('There is no any common substring according to the parametres given')

common_substrings('ciguliuana','ciguana')
common_substrings('apples','appleses')
common_substrings('apple pie available','apple pies')
serko
quelle
0

Als ob diese Frage nicht genügend Antworten hätte, gibt es noch eine andere 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]

Einige Beispielfälle:

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

mr.plow
quelle
0
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]
JiPiBi
quelle
-1

Zunächst wird eine Helferfunktion von den angepassten itertools paarweise Rezept zu produzieren Substrings.

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)

Dann iteriert eine Funktion über Teilzeichenfolgen, die längste zuerst, und testet die Mitgliedschaft. (Effizienz nicht berücksichtigt)

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
>>> 
wwii
quelle
-1
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))
user3838498
quelle