- int* Getnext(char *p,int len_p){//p 为模式串
- int *Next = new int[len_p];
- Next[0] = -1;
- int j = -1,i=0;
- while(i <len_p){// 自身与自身匹配
- while(j != -1&&p[j]!=p[i])// 移动匹配串
- j = Next[j];
- j+=1;
- Next[++i] = j;
- }
- return Next;
- }
- vector<int>* Kmp(char *s,char *p,int len_s,int len_p){//s 为主串, p 为匹配串
- int *Next = Getnext(p,len_p);// 求得 Next 数组
- int j = 0;//j 为匹配串匹配到的位置
- vector<int>* ans = new vector<int>();//ans 为匹配到的主串的开头下标位置
- for(int i=0;i <len_s;i++){
- while(j != -1 && s[i] != p[j])
- j = Next[j];
- j+=1;
- if(j == len_p){// 匹配串匹配完毕
- ans->push_back(i - len_p + 1);
- j = Next[j];//j 退回到 Next[j]
- }
- }
- return ans;
- }
来源: http://www.bubuko.com/infodetail-2529361.html