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])接下来每行代表一次匹配操作,黄色部分代表匹配成功的部分,红色字符为发现的第一个 ...