推荐本书

扫码查看
推荐本书,Grokking.Algorithms.An.illustrated.guide.for.programmers.and.other.curious.people
这本书很不错,讲的通俗易懂。而且都是实际的利用数据结构和算法解决问题,而没有把重点放在数据结构本身的实现上。

下面是两段代码分别是计算longest_common_substring和longest_common_subsequence.

点击(此处)折叠或打开

  1. #https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring#Python_3
  2. def longest_common_substring(s1,s2):
  3.     m=[[0] *(1+len(s2)) for i in range(1+len(s1))]
  4.     longest,x_longest=0,0
  5.     for x in range(1,1+len(s1)):
  6.         for y in range(1,1+len(s2)):
  7.             if s1[x-1] == s2[y-1]:
  8.                 m[x][y]=m[x-1][y-1]+1
  9.                 if m[x][y] > longest:
  10.                     longest=m[x][y]
  11.                     x_longest=x
  12.             else:
  13.                 m[x][y]=0
  14.     return s1[x_longest-longest: x_longest]

  15. print(longest_common_substring("blue","clues"))

  16. def longest_common_subsequence(s1,s2):
  17.     m=[[0] *(1+len(s2)) for i in range(1+len(s1))]
  18.     longest=0
  19.     for x in range(1,1+len(s1)):
  20.         for y in range(1,1+len(s2)):
  21.             if s1[x-1] == s2[y-1]:
  22.                 m[x][y]=m[x-1][y-1]+1
  23.                 if m[x][y] > longest:
  24.                     longest=m[x][y]

  25.             else:
  26.                 m[x][y]=max(m[x-1][y],m[x][y-1])
  27.     return longest

  28. print(longest_common_subsequence("blue","clues"))
  29. print(longest_common_subsequence("fish","fosh"))
  30. 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/

10-12 09:46
查看更多