wake-up-neo.com

Finden Sie einen gemeinsamen Teilstring zwischen zwei Zeichenfolgen

Ich möchte zwei Saiten miteinander vergleichen und die Übereinstimmung beibehalten, wo der Vergleich fehlschlägt.

Wenn ich also 2 Saiten habe -

string1 = apples
string2 = appleses

answer = apples

Ein anderes Beispiel, da der String mehr als ein Wort haben könnte. 

string1 = Apple pie available
string2 = Apple pies

answer = Apple pie

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

45
NorthSide

Es heißt Longest Common Substring Problem. Hier präsentiere ich eine einfache, leicht verständliche, aber ineffiziente Lösung. Es dauert lange, bis eine korrekte Ausgabe für große Strings erzeugt wird, 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
13
thefourtheye

Der Vollständigkeit halber enthält difflib in der Standardbibliothek eine Vielzahl von Dienstprogrammen zum Sequenzvergleich. Zum Beispiel find_longest_match , das bei Strings den längsten gemeinsamen Teilstring findet. 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
101
RickardSjogren
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 auf etwas fremde Weise:

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

Was 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))
29
Eric

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

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

Das gleiche wie Evo's , jedoch mit einer beliebigen Anzahl von zu vergleichenden Strings:

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())
5
SergeyR

Beheben Sie Fehler mit der ersten Antwort:

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

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 vom Anfang beider Strings aus.

1
Birei

Dies ist nicht der effizienteste Weg, aber ich könnte mir das vorstellen und es funktioniert. Wenn jemand es verbessern kann, tun Sie dies bitte. Was es tut, ist, dass es eine Matrix bildet und 1 gibt, wo die Zeichen übereinstimmen. Dann scannt er die Matrix nach der längsten Diagonale von 1s und verfolgt, wo sie beginnt und endet. Dann gibt es den Teilstring der Eingabezeichenfolge mit den Start- und Endpositionen als Argumente zurück.

Hinweis: Dadurch wird nur eine längste gemeinsame Teilzeichenfolge gefunden. Wenn mehr als ein Feld vorhanden ist, können Sie ein Array erstellen, in dem die Ergebnisse gespeichert werden, und es wird zurückgegeben.

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
1
Rali Tsanova
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     
1
radhikesh93
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))
0
user3838498

Dies ist das Klassenzimmerproblem, das als "Longest Sequence Finder" bezeichnet wird. Ich habe einen einfachen Code gegeben, der für mich funktioniert hat, auch meine Eingaben enthalten eine Liste 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
0
Bantu Manjunath

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

Zuerst eine helper - Funktion, die aus dem itertools paarweisen Rezeptur angepasst wurde, um Teilstrings zu erzeugen.

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 eine Funktion, die die Teilstrings durchläuft, die längste zuerst und die Mitgliedschaft testet. (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
>>> 
0
wwii