Как найти самое длинное пересечение между двумя строками в python? - PullRequest
Новая
       13

Как найти самое длинное пересечение между двумя строками в python?

1 голос
/ 23 апреля 2020

Я пытаюсь написать программу, которая нашла бы самое длинное пересечение между двумя строками. Условия:

  1. Если общего символа нет, программа возвращает пустую цепочку.
  2. Если имеется несколько подстрок общих символов одинаковой длины, она должна возвращать, в зависимости от того, что является Наибольшие, например, для "bbaa cc" и "aabb" повторяющиеся подстроки - "aa" и "bb", но как "bb"> "aa", поэтому программы должны возвращать только "bb".
  3. Наконец, программа должна возвращать самую длинную общую подстроку, например, для «программы» и «грамматики», возвращаемое значение должно быть «грамм», а не «грамм».

В моем коде есть проблема с этим последним условием, как я могу изменить его, чтобы он работал как положено? 

def intersection(v, w):
    if not v or not w:
        return ""
    x, xs, y, ys = v[0], v[1:], w[0], w[1:]
    if x == y:
        return x + intersection(xs, ys)
    else:
        return max(intersection(v, ys), intersection(xs, w), key=len)

Драйвер: 

print(intersection('programme', 'grammaire'))
...