字符串匹配_暴力匹配算法

字符串匹配_暴力匹配算法

假设现在我们面临这样一个问题：有一个文本串S，和一个模式串P，现在要查找P在S中的位置，怎么查找呢？

首先，先理清楚了暴力匹配算法的流程及内在的逻辑：

如果用暴力匹配的思路，并假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置，则有：

如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符； 如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。

举个例子，如果给定文本串S：“BBC ABCDAB ABCDABCDABDE”，和模式串P：“ABCDABD”，现在要拿模式串P去跟文本串S匹配，整个过程如下所示：

3.直到S[4]跟P[0]匹配成功（i=4，j=0），此时按照上面的暴力匹配算法的思路，转而执行第①条指令：“如果当前字符匹配成功（即S[i] == P[j]），则i++，j++”，可得S[i]为S[5]，P[j]为P[1]，即接下来判断S[5]跟P[1]是否匹配（i=5，j=1）

java代码如下

package queueDemo;public class kmpdemo02 { public static void main(String[] args) { String str1 = "你我他"; String str2 = "他"; int index = kmpdemo02(str1,str2); System.out.println(index); } public static int kmpdemo02(String str1,String str2) { char[] s1 = str1.toCharArray(); char[] s2 = str2.toCharArray(); int s1len = s1.length; int s2len = s2.length; int i = 0; int j = 0; while(i < s1len && j < s2len) { if(s1[i] == s2[j]) { i++; j++; }else { i = i - j + 1;j = 0; } } if(i == s1len) { return i - j; }else { return -1; } }}

c

#define MAXLEN 100typedef struct{ char ch[MAXLEN]; int length;}String;int index(String s1,String s2){ int i = 0; int j = 0; while(i < s1.length && j < s2.length){ if(s1.ch[i] == s2.ch[j]){ i++; j++;}else{ i = i - j + 1; j = 1; } } if(i == s1.length){ return i - j; }else{ return -1; }}

最后分析时间复杂度

我们设子串长为m，母串长为n，同时m比n小的多。 在最好情况下，子串与母串的失配都是发生在第一个字符处，时间复杂度为O(m+n)。 在最坏的情况下，即子串每一次与母串失配都是在最后一个字母时，时间复杂度为O((m*n)。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。