IBOutlet
один раз, метку IBOutlet
, что ваш ivar не нужен. UIViewController
? В какой-то момент вы должны называть [SecondView initWithNibName:@"yourNibName" bundle:nil];
Его называют самой длинной общей проблемой подстроки. Здесь я представляю простое, понятное, но неэффективное решение. Это потребует много времени для создания правильного вывода для больших строк, так как сложность этого алгоритма равна O (N ^ 2).
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")
Выход
apple pie
apples
apples
Попробуйте:
import itertools as it
''.join(el[0] for el in it.takewhile(lambda t: t[0] == t[1], zip(string1, string2)))
Выполняет сравнение с началом обеих строк.
it.takewhile
для языка: a for a, b in zip(string1, string2) while a == b
– Eric
10 September 2013 в 12:23
''.join(el[0] for el in itertools.takewhile(lambda t: t[0] == t[1], zip("ahello", "hello")))
возвращает ""
, что кажется неправильным. Правильный результат будет "hello"
.
– Anderson Green
26 January 2015 в 06:43
То же, что и Evo's , но с произвольным числом строк для сравнения:
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())
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 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'
Или немного страннее:
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))
Что может быть более читаемым как
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))
Raising the StopIteration exception inside a generator will now generate a DeprecationWarning
. Если вы запускаете свой код с помощью Python3 -W default::DeprecationWarning
, последние два примера поднимают DeprecationWarning
s
– jpyams
20 December 2017 в 17:10
Это не самый эффективный способ сделать это, но это то, что я мог придумать, и он работает. Если кто-то может его улучшить, пожалуйста. Что он делает, так это делает матрицу и ставит 1, где совпадают символы. Затем он сканирует матрицу, чтобы найти самую длинную диагональ 1 с, отслеживая, где она начинается и заканчивается. Затем он возвращает подстроку входной строки с начальным и конечным позициями в качестве аргументов.
Примечание. Это находит только одну самую длинную общую подстроку. Если есть более одного, вы можете создать массив для хранения результатов и вернуть его. Кроме того, он чувствителен к регистру, поэтому (Apple pie, apple pie) вернет pple pie.
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
Для полноты difflib
в стандартной библиотеке содержится множество утилит сравнения последовательностей. Например, find_longest_match
, который находит самую длинную общую подстроку при использовании в строках. Пример использования:
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 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")
Сначала функция помощника , адаптированная из парного рецепта itertools для создания подстрок.
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)
Затем функция выполняет итерацию по подстрокам, самая длинная во-первых, и тесты для членства. (эффективность не учитывается)
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
>>>
Возвращает первую длинную общую подстроку:
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
i+j < len1
– REALFREE 9 July 2014 в 07:47x = "cov_basic_as_cov_x_gt_y_rna_genes_w1000000" y = "cov_rna15pcs_as_cov_x_gt_y_rna_genes_w1000000"
– Dima Lituiev 22 February 2016 в 19:51