python implements a method to find the longest textual subsequence
- 2020-10-31 21:49:04
- OfStack
This instance for share python realize the back to the longest sequence of fa, this one problem of a class can use dynamic programming method to do it, there should be a few before I post are all about palindrome sequence to solve, have the very can reuse of code to write in other ways, ready-made, his mind is still sliding window section, will be more is simple operation, the following is the specific implementation:
#!usr/bin/env python
#encoding:utf-8
'''''
__Author__: More cold city
Function: Find the longest text subsequence
'''
def slice_window(one_str,w=1):
'''''
Sliding window function
'''
res_list=[]
for i in range(0,len(one_str)-w+1):
res_list.append(one_str[i:i+w])
return res_list
def is_huiwen(one_str_list):
'''''
The input 1 A list of strings to determine if they are palindromes
'''
if len(one_str_list)==1:
return True
else:
half=len(one_str_list)/2
if len(one_str_list)%2==0:
first_list=one_str_list[:half]
second_list=one_str_list[half:]
else:
first_list=one_str_list[:half]
second_list=one_str_list[half+1:]
if first_list==second_list[::-1]:
return True
else:
return False
def find_longest_sub_palindrome_str(one_str):
'''''
The main function , Look for the longest textual subsequence
'''
all_sub=[]
for i in range(1,len(one_str)):
all_sub+=slice_window(one_str,i)
all_sub.append(one_str)
new_list=[]
for one in all_sub:
if is_huiwen(list(one)):
new_list.append(one)
new_list.sort(lambda x,y:cmp(len(x),len(y)),reverse=True)
print new_list[0]
if __name__ == '__main__':
one_str_list=['uabcdcbaop','abcba','dmfdkgbbfdlg','mnfkabcbadk']
for one_str in one_str_list:
find_longest_sub_palindrome_str(one_str)
The results are as follows:
[
abcdcba
abcba
bb
abcba
[Finished in 0.3s]