0.前言 距离上一次分析算法已经过去好几年了- -以我的算法水平其实是很讨厌分析算法的，一个是想写明白耗时很长，一个是说人话很啰嗦。但是写代码或公式又大部分人很难理解。今天要分析的算法是字符串相似度，Levenshtein距离 形式化描述：给定字符串strA,strB,求解dist(strA,strB)的值,dist为Levenshtein距离 说人话：两个字符串，编辑几次能变得完全一样，编辑允许的操作(插入，删除，替换字符) 0.定理/公理，人人都能看懂的情况 字符串基本操作： 连接 下文用+代表 删除字符 下文用 删除strA[0]表示 增加字符 下文用 str[x]=’ ...
2015.11.6.KMP算法
KMP算法是要解决的问题是一个字符串中查找指定子串的问题。由于臻臻问我这个问题，所以我不得不再次看看KMP -_-|| ，同时感谢袁涛和王宇晖Orz，（另：默默等待王霸的KMP第三层优化，但愿他能成功）。 本人水平不高，有写错的地方还请批评指正。 先说传统的匹配算法。以图中的字符串为例，第一行是要匹配的目标字符串（称之为主串。其中第i个简写为S[i])，要匹配的字符串称之为子串（也叫模式串，其中第i个简写为P[i]）接下来每行代表一次匹配操作，黄色部分代表匹配成功的部分，红色字符为发现的第一个 ...
