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.
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
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
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))
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'
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())
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")
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.
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
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
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))
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
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
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
>>>