//代码1-1 //int search(char const*, int, char const*, int) //查找出模式串patn在主串src中第一次出现的位置 //plen为模式串的长度 //返回patn在src中出现的位置,当src中并没有patn时,返回-1 int search(char const* src, int slen, char const* patn, int plen) { int i = 0, j = 0; while( i < slen && j < plen ) { if( src[i] == patn[j] ) //如果相同,则两者++,继续比较 { ++i; ++j; } else { //否则,指针回溯,重新开始匹配 i = i - j + 1; //退回到最开始时比较的位置 j = 0; } } if( j >= plen ) return i - plen; //如果字符串相同的长度大于模式串的长度,则匹配成功 else return -1; }
回溯法字符串匹配算法就是用一个循环来找出所有有效位移,该循环对n-m+1个可能的位移中的每一个index值,检查条件为P[0…m-1]=
S[index…index+m-1](因为模式串的长度是m,索引范围为0…m-1)。
该算法思维比较简单(但也常被一些公司做为面试题),很容易分析出本算法的时间复杂度为O(pattern_length*target_length)