Самая длинная общая подстрока больше чем от двух строк - Python
Я ищу библиотеку Python для нахождения самой длинной общей подстроки от ряда строк. Существует два способа решить эту проблему:
- использование суффиксных деревьев
- использование динамического программирования.
Реализованный метод не важен. Важно, чтобы это могло использоваться для ряда строк (не только две строки).
3 ответа
Эти парные функции найдут самую длинную общую строку в любом произвольном массиве строк:
def long_substr(data):
substr = ''
if len(data) > 1 and len(data[0]) > 0:
for i in range(len(data[0])):
for j in range(len(data[0])-i+1):
if j > len(substr) and is_substr(data[0][i:i+j], data):
substr = data[0][i:i+j]
return substr
def is_substr(find, data):
if len(data) < 1 and len(find) < 1:
return False
for i in range(len(data)):
if find not in data[i]:
return False
return True
print long_substr(['Oh, hello, my friend.',
'I prefer Jelly Belly beans.',
'When hell freezes over!'])
Без сомнения, алгоритм можно улучшить, и я мало знаком с Python, так что, возможно, он мог бы быть более эффективным синтаксически, но он должен выполнять свою работу.
РЕДАКТИРОВАТЬ: встраивает вторую функцию is_substr, как продемонстрировал Дж. Ф. Себастьян. Использование остается прежним. Примечание: без изменений в алгоритме.
def long_substr(data):
substr = ''
if len(data) > 1 and len(data[0]) > 0:
for i in range(len(data[0])):
for j in range(len(data[0])-i+1):
if j > len(substr) and all(data[0][i:i+j] in x for x in data):
substr = data[0][i:i+j]
return substr
Надеюсь, это поможет,
Джейсон.
# this does not increase asymptotical complexity
# but can still waste more time than it saves. TODO: profile
def shortest_of(strings):
return min(strings, key=len)
def long_substr(strings):
substr = ""
if not strings:
return substr
reference = shortest_of(strings) #strings[0]
length = len(reference)
#find a suitable slice i:j
for i in xrange(length):
#only consider strings long at least len(substr) + 1
for j in xrange(i + len(substr) + 1, length + 1):
candidate = reference[i:j] # ↓ is the slice recalculated every time?
if all(candidate in text for text in strings):
substr = candidate
return substr
Заявление об ограничении ответственности Это очень мало добавляет к ответу jtjacques. Однако, надеюсь, это должно быть более читабельным и быстрее и , это не вписывается в комментарий, поэтому я публикую это в ответе. Честно говоря, меня не устраивает short_of .
def common_prefix(strings):
""" Find the longest string that is a prefix of all the strings.
"""
if not strings:
return ''
prefix = strings[0]
for s in strings:
if len(s) < len(prefix):
prefix = prefix[:len(s)]
if not prefix:
return ''
for i in range(len(prefix)):
if prefix[i] != s[i]:
prefix = prefix[:i]
break
return prefix
Из http://bitbucket.org/ned/cog/src/tip/cogapp/whiteutils.py