江苏省网站建设与管理历年自考试题,车网站模板预览,做电商怎么自学,百度游戏风云榜朴素的字符串匹配算法又称为暴力匹配算法#xff08;Brute Force Algorithm#xff09;#xff0c;最为简单的字符串匹配算法。算法简介朴素的字符串匹配算法又称为暴力匹配算法#xff08;Brute Force Algorithm#xff09;#xff0c;它的主要特点是#xff1a;没有预…朴素的字符串匹配算法又称为暴力匹配算法Brute Force Algorithm最为简单的字符串匹配算法。算法简介朴素的字符串匹配算法又称为暴力匹配算法Brute Force Algorithm它的主要特点是没有预处理阶段滑动窗口总是后移 1 位对模式中的字符的比较顺序不限定可以从前到后也可以从后到前匹配阶段需要 O((n - m 1)m) 的时间复杂度需要 2n 次的字符比较很显然朴素的字符串匹配算法 NAIVE-STRING-MATCHER 是最原始的算法它通过使用循环来检查是否在范围 n-m1 中存在满足条件 P[1..m] T [s 1..s m] 的有效位移 s。伪代码如下NAIVE-STRING-MATCHER(T, P)n ← length[T]m ← length[P]for s ← 0 to n - mdoif P[1.. m] T[s 1.. s m]then print Pattern occurs with shift s如上图中对于模式 P aab 和文本 T acaabc将模式 P 沿着 T 从左到右滑动逐个比较字符以判断模式 P 在文本 T 中是否存在。可以看出NAIVE-STRING-MATCHER 没有对模式 P 进行预处理所以预处理的时间为 0。而匹配的时间在最坏情况下为 Θ((n-m1)m)如果 m [n/2]则为 Θ(n2)。图例分析假设有两个字符串Mabcdefabcdx;Tabcdx;想要找到T串在M串中的位置要怎么找呢也就是说从主串M的第一个字符开始分别与子串从开头进行比较当发现不匹配时主串回到这一轮开始的下一个字符子串从头开始比较。直到子串所有的字符都匹配返回所在主串中的下标。算法复杂度假设S的长度是mT的长度是n暂不考虑pos从字符串S的开头开始比较。最好的情况是第一次就匹配了需要比较的次数是n.最坏的情况下就是上面举的这种例子需要把整个字符串都比较完从下面的代码中就体现为把两层循环都跑了一遍。这时候比较的次数就是t*(s-t1).所以这个算法的(最坏)时间复杂度就是o(t(s-t1))近似为o(n2).
