Я сделал алгоритм грубой силы, чтобы найти самый длинный палиндром в строке. Этот палиндром является подстрокой ввода. Ниже приведен код.
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()
```