字符串相关问题 及 后缀树

这一节主要简单讨论几个跟字符串相关的问题，主题可能会在后面陆续增加。

子串问题用的最多的方法就是动态规划算法和后缀树（见文尾）、Trie。当然其他如hash table，堆等等也需要考虑。有时也可能要配合MAP使用。

1 字符串精确匹配

1.1 KMP算法

　　KMP主要是利用模式串的最大相同后缀前缀长度。有了模式串在各个位置的这个长度，当与目标串在某个位置不匹配时，可以跳过模式串的这个长度的距离，避免重复的字符串比较。模式串的最大相同后缀前缀长度序列的构建，其实跟后面字符串匹配类似，只是把目标串换成了自己。

详情参照“从头到尾彻底理解KMP”：http://www.cnblogs.com/zhangtianq/p/5839909.html

1.2 连续子串

单个或多个字符串的最长连续重复子串：后缀树

重复次数达到k次的子串：后缀树

最长回文子串：动态规划，Manacher法

2 字符串模糊匹配

2.1 k-近似匹配（允许k个不匹配）：

　　　字符串S和P的编辑距离k：动态规划，dist[i][j] = min(dist[i-1][j] + 1, dist[i][j-1] + 1, dist[i-1][j-1] + (S[i]==P[j])?0:1)

　　　做一下改进用于k-近似匹配，参考 “动态规划 近似串匹配”。主要区别是第一行的初始值不一样。算完整串的编辑距离，S[i]与P的空子串的编辑距离是i，而k-近似匹配时，因为S的子串可以从任意位置开　       始，所以初始编辑距离为0。

　　　或者通过后缀树，查找节点的最近公共父节点（待考）

2.2 固定空隙长度子串（k个%， maximal gapped motifs)

 　　后缀树相关（待补充）

2.3 随机空隙长度子串（*）

　　动态规划：字符串S和模式p，当p[j]==‘*’，dp[i][j]=1 if dp[i][j-1] or dp[i-1][j-1]。若此时dp[i][j]==1，则dp[i~n][j]=1

2.4 最长公共子序列LCS

 类似上面编辑距离， A和B的LCS[i][j] = (A[i]==B[j])? 1+LCS[i-1][j-1] : max(LCS[i-1][j], LCS[i][j-1]),

3 词频统计

 Trie（前缀树/字典树）及其应用 应用场景3

其他参考

后缀树及模式匹配 https://wenku.baidu.com/view/75ae114cc850ad02de804110.html

“in the search of motifs (and other hidden structures)”：http://www.doc88.com/p-9923369128588.html

维基百科“Suffix tree”：https://en.wikipedia.org/wiki/Suffix_tree

http://blog.sina.com.cn/s/blog_a02991400101gl3o.html

Suffix tree

Notes

  1. Mansour et al. (2011).

References

External links

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/justinh/p/7776873.html