当前位置: 编程技术>c/c++/嵌入式
深入串的模式匹配算法(普通算法和KMP算法)的详解
来源: 互联网 发布时间:2014-10-16
本文导语: 串的定位操作通常称作串的模式匹配,是各种处理系统中的最重要操作之一。模式匹配最朴素的算法是回溯法,即模式串跟主串一个字符一个字符的匹配,当模式串中跟主串不匹配时,主串回溯到与模式串匹配开始的下一个位...
串的定位操作通常称作串的模式匹配,是各种处理系统中的最重要操作之一。
模式匹配最朴素的算法是回溯法,即模式串跟主串一个字符一个字符的匹配,当模式串中跟主串不匹配时,主串回溯到与模式串匹配开始的下一个位置,模式串回溯到第一个位置,继续匹配。算法的时间复杂度为O(m*n),算法如下:
//朴素的串的模式匹配算法,S为主串,T为模式串,即找S中有没有与T相同的字串
int Index(char *S, char *T, int pos)//pos记录从哪一位开始匹配可以直接用0代替
{
int i=pos, j=0;
while(i
模式匹配最朴素的算法是回溯法,即模式串跟主串一个字符一个字符的匹配,当模式串中跟主串不匹配时,主串回溯到与模式串匹配开始的下一个位置,模式串回溯到第一个位置,继续匹配。算法的时间复杂度为O(m*n),算法如下:
代码如下:
//朴素的串的模式匹配算法,S为主串,T为模式串,即找S中有没有与T相同的字串
int Index(char *S, char *T, int pos)//pos记录从哪一位开始匹配可以直接用0代替
{
int i=pos, j=0;
while(i