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.
string1 = bapples
undstring2 = cappleses
?os.path.commonprefix(['apples', 'appleses']) -> 'apples'
`Antworten:
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
quelle
i+j < len1
x = "cov_basic_as_cov_x_gt_y_rna_genes_w1000000" y = "cov_rna15pcs_as_cov_x_gt_y_rna_genes_w1000000"
Der Vollständigkeit
difflib
halber bietet die Standardbibliothek eine Vielzahl von Dienstprogrammen zum Vergleichen von Sequenzen. Zum Beispiel,find_longest_match
das 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
quelle
find_longest_match()
nicht das, was sein Name impliziert. Die Klassendokumentation fürSequenceMatcher
weist jedoch darauf hin und sagt :This does not yield minimal edit sequences
. In einigen Fällenfind_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.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))
quelle
Raising the StopIteration exception inside a generator will now generate a DeprecationWarning
. Wenn Sie Ihren Code mit ausführenPython3 -W default::DeprecationWarning
,DeprecationWarning
Man könnte auch in Betracht ziehen,
os.path.commonprefix
dass 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.
quelle
os.commonpath
nicht mit deros.commonprefix
in der Antwort verwendeten übereinstimmt . Aber wahr, es könnte einige Einschränkungen geben, nur die Dokumentation erwähnt keine.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())
quelle
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")
quelle
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.
quelle
it.takewhile
eine Sprachfunktion erstellt:a for a, b in zip(string1, string2) while a == b
''.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"
.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
quelle
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.
quelle
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'}
quelle
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
quelle
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
quelle
**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
quelle
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
quelle
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')
quelle
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'
quelle
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]
quelle
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 >>>
quelle
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))
quelle