串的模式匹配算法

串的匹配算法——BruteForce(BF)算法匹配模式的定义设有主串S和子串T，子串T的定位就是要在主串S中找到一个与子串T相等的子串。通常把主串S称为目标串，把子串T称为模式串，因此定位也称作模式匹配。模式匹配成功是指在目标串S中找到一个模式串T；不成功则指目标串S中不存在模式串T。BF算法Brute-Force算法简称为BF算法，其基本思路是：从目标串S的第一个字符开始和模式串T中的第一个字符比较，若相等，则继续逐个比较后续的字符；否则从目标串S的第二个字符开始重新与模式串T的第一个字符进行比较。以此类推，若从模式串T的第i个字符开始，每个字符依次和目标串S中的对应字符相等，则匹配成功，该算法返回i；否则，匹配失败，算法返回0。实现代码如下：/*返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0./*T非空。intindex(StringS,StringT,intpos){inti=pos;//用于主串S中当前位置下标，若pos不为1则从pos位置开始匹配intj=1;//j用于子串T中当前位置下标值while(i=S[0]&&j=T[0])//若i小于S长度且j小于T的长度时循环{if(S[i]==T[j])//两个字母相等则继续{++i；++j；}else//指针后退重新开始匹配{i=i-j+2;//i退回到上次匹配首位的下一位j=1；}if(jT[0])returni-T[0];elsereturn0;}}BF算法的时间复杂度若n为主串长度，m为子串长度则最好的情况是：一配就中，只比较了m次。最坏的情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位比较了m次，最后m位也各比较了一次，还要加上m,所以总次数为：(n-m)*m+m=(n-m+1)*m从最好到最坏情况统计总的比较次数，然后取平均，得到一般情况是O(n+m).