2016-08-17 8 views
0

Когда я запускаю LCS («человек», «шимпанзе»), я получаю «h» вместо «hm». Когда я запускаю LCS ('gattaca', 'tacgaacta'), я получаю «g» вместо «gaaca». Когда я запускаю LCS («wow», «whew»), я получаю «ww», что является правильным. Когда я запускаю LCS ('', 'whew'), я получаю "", что является правильным. Когда я запускаю LCS ('abcdefgh', 'efghabcd'), я получаю «a» вместо «abcd». Что я делаю неправильно?Самая длинная общая подпоследовательность Функция Python 2

Вот мой код:

def LCS(S, T): 
    array = '' 
    i = 0 
    j = 0 
    while i < len(S): 
    while j < len(T): 
     if S[i] == T[j]: 
     array += S[i] 
     j += 1 
    i += 1 
    return array 
+1

reset j в конце второго цикла while –

+0

Почему вы ожидали, что это сработает? – user2357112

+1

@RahulMadhavan: Нет, все еще совершенно неправильно. Этот код на самом деле не спасен; любая фиксированная версия будет по существу полной перезаписи. – user2357112

ответ

0

Приобретено благодаря людям, находящимся рядом со мной в лаборатории! Также было бы неплохо, если бы время от времени не приходилось сталкиваться с заносчивыми людьми в Stack Overflow.

def LCS(S, T): 
    # If either string is empty, stop 
    if len(S) == 0 or len(T) == 0: 
    return "" 

    # First property 
    if S[-1] == T[-1]: 
    return LCS(S[:-1], T[:-1]) + S[-1] 

    # Second proprerty 
    # Last of S not needed: 
    result1 = LCS(S[:-1], T) 
    # Last of T not needed 
    result2 = LCS(S, T[:-1]) 
    if len(result1) > len(result2): 
    return result1 
    else: 
    return result2 
0

Это не то, как вы пишете LCS. Вот как вы пишете очень странную функцию, которая вычисляет количество букв во второй строке, которые равны первой букве первой строки.

Я считаю, что то, что вы хотели написать, неверно, так что это не имеет значения, но если бы я правильно догадался, что вы хотели написать, вы забыли назначить 0 в j внутри внешнего цикла while.