Совпадение символов строки в другой строке в том же порядке в Python - PullRequest
Новая
       32

Совпадение символов строки в другой строке в том же порядке в Python

0 голосов
/ 20 мая 2019

Это довольно простой вопрос, но я нигде не могу найти правильный ответ.У меня есть 2 строки одинаковой длины в Python, и я хотел бы найти, если хотя бы n символов (n может быть любым числом, меньшим длины строки) первой строки содержатся (в том же порядке) во второй.

например: 

s1 = 'TAGCACTTT'
s2 = 'CGATGATTT'
s3 = 'AGACGGCCT'
n = 6

совпадение s1 и s2 должно возвращать True, поскольку s2 содержит буквы 'AGATTT' в порядке, в то время как совпадение s1 и s3 должно возвращать False, потому что совпадение только 5 букв.Как мне сделать это эффективно?

1 Ответ

0 голосов
/ 20 мая 2019 
def max_sub(X, Y, m, n):
    if m == 0 or n == 0:
        return 0;
    elif X[m - 1] == Y[n - 1]:
        return 1 + max_sub(X, Y, m - 1, n - 1);
    else:
        return max(max_sub(X, Y, m, n - 1), max_sub(X, Y, m - 1, n))

s1 = 'TAGCACTTT'
s2 = 'CGATGATTT'
s3 = 'AGACGGCCT'
n = 6

# Permutations using library function
from itertools import permutations

# Get all permutations of [s1,s2,s3]
perm = permutations([s1, s2, s3],2)

# pass over the obtained permutations
for i in list(perm):
    len_ = max_sub(i[0], i[1], len(i[0]), len(i[1]))
    if len_ >= n:
        print("For {},{} length of common substring is: {}, True ".format(i[0], i[1], max_sub(i[0], i[1], len(i[0]), len(i[1]))))
    else:
        print("For {},{} length of common substring is: {}, False ".format(i[0], i[1], max_sub(i[0], i[1], len(i[0]), len(i[1]))))

вывод: 

For TAGCACTTT,CGATGATTT length of common substring is: 6, True 
For TAGCACTTT,AGACGGCCT length of common substring is: 5, False 
For CGATGATTT,TAGCACTTT length of common substring is: 6, True 
For CGATGATTT,AGACGGCCT length of common substring is: 4, False 
For AGACGGCCT,TAGCACTTT length of common substring is: 5, False 
For AGACGGCCT,CGATGATTT length of common substring is: 4, False
...