Question

求出首次与字符串匹配的起始位置的代码，要在c++里实现的。

从串s1中第k个字符起，求出首次与字符串s2匹配的起始位置。要包含的算法有：朴素模式匹配，给定位置的串匹配，kmp算法。要在c++中实现的。谢谢啦

Answer 1

1.朴素的模式匹配也叫B-F算法int Find{int i,j;for(i=0;i<=curLength-pat.curLength;i++)//curlength是目标串的长度，pat.Length是模式串的长度{for(j=0;j<=pat.curlength;j++)//从ch[i] 开始的子串与模式串pat.ch进行比较if(ch[i+j]!=pat.ch[j])break;//ch是存放字符串的指针if(j==pat.curlength)return i;}return -1//找不到返回-1} 2. KMP算法(最大特点是不回溯)int fastFind(int next[]){int posP=0;posT=0;//两个串的扫描指针int lengthP=pat.curLength;int lengthT=curLength;while(posP<lengthP&&posT<lengthT)if(posP==-1||pat.ch[posP]==ch[posT]){posP++;posT++;}else posP=next[posP];if(posP<lengthP)return -1;//失败else return posT-lengthP;} //计算next[j]的算法void getNext(int next[]){int j=0,k=-1,lengthP=curLength;next[0]=-1;while(j<lengthP)if(k==-1||ch[j]==ch[k]){j++;k++;</p><p>next[j]=k;</p><p>}else k=next[k];}只是思路，不能直接上机实现，如果你能理解next[j]的原理，就很简单了，希望对你有帮助。