这本书很不错,讲的通俗易懂。而且都是实际的利用数据结构和算法解决问题,而没有把重点放在数据结构本身的实现上。
下面是两段代码分别是计算longest_common_substring和longest_common_subsequence.
点击(此处)折叠或打开
- #https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring#Python_3
- def longest_common_substring(s1,s2):
- m=[[0] *(1+len(s2)) for i in range(1+len(s1))]
- longest,x_longest=0,0
- for x in range(1,1+len(s1)):
- for y in range(1,1+len(s2)):
- if s1[x-1] == s2[y-1]:
- m[x][y]=m[x-1][y-1]+1
- if m[x][y] > longest:
- longest=m[x][y]
- x_longest=x
- else:
- m[x][y]=0
- return s1[x_longest-longest: x_longest]
- print(longest_common_substring("blue","clues"))
- def longest_common_subsequence(s1,s2):
- m=[[0] *(1+len(s2)) for i in range(1+len(s1))]
- longest=0
- for x in range(1,1+len(s1)):
- for y in range(1,1+len(s2)):
- if s1[x-1] == s2[y-1]:
- m[x][y]=m[x-1][y-1]+1
- if m[x][y] > longest:
- longest=m[x][y]
- else:
- m[x][y]=max(m[x-1][y],m[x][y-1])
- return longest
- print(longest_common_subsequence("blue","clues"))
- print(longest_common_subsequence("fish","fosh"))
- print(longest_common_subsequence("fort","fosh"))
https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python
计算两个词之间的相似程度。
Linux 文件系统规范,我记得有这么个东西的。
https://www.blackmoreops.com/2015/06/18/linux-file-system-hierarchy-v2-0/