Алгоритм для самого длинного палиндрома

Я сделал алгоритм грубой силы, чтобы найти самый длинный палиндром в строке. Этот палиндром является подстрокой ввода. Ниже приведен код.


def generate_substrings(string):
    """
    avg time: O(len(string) * len(string))
    avg space: O(1) 
    
    amortized time: O(len(string) * len(string)) 
    amortized space: O(1) 
    """ 
    col = 0 
    for row in range(len(string)):
        col = row + 1 
        while col < len(string) + 1:
            yield string[row:col]
            col = col + 1 
            
def test_generate_substrings():
    assert list(generate_substrings('')) == []
    assert list(generate_substrings('a')) == ['a']
    assert list(generate_substrings('ab')) == ['a', 'ab', 'b']

def is_palindrome(string):
    """
    avg time: O(len(string)) 
    avg space: O(len(string)) 
    
    amortized time: O(len(string)) 
    amortized space: O(len(string)) 
    """
    return string[::-1] == string 

def test_is_palindrome():
    assert is_palindrome('') == True 
    assert is_palindrome('ab') == False 
    assert is_palindrome('bb') == True 
    assert is_palindrome('abc') == False 
    assert is_palindrome('ddd') == True 
    
def find_palindrome(string):
    """
    avg time: O(len(string) * len(string)) 
    avg space: O(len(string)) 
    
    amortized time: O(len(string) * len(string)) 
    amortized space: O(len(string))
    """
    answer=""
    vec = [] 
    
    for string in generate_substrings(string):
        if is_palindrome(string):
            vec.append(string)
    
    for string in vec:
        if len(answer) <= len(string):
            answer = string 
       
    return answer 

def test_find_palindrome():
    assert find_palindrome('ab') == 'b'
    assert find_palindrome('aa') == 'aa' 

def main():
"""
entry point for test code 
"""
    test_generate_substrings() 
    test_is_palindrome() 
    test_find_palindrome() 

if __name__ == '__main__':
    main()
 
```

0

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *