白鸽

用户名：zhx123

访问量：61365

签　名：

一个认真的求学者

等　　级
排　　名	25
经　　验	16711
参赛次数	4
文章发表	280
年　　龄	25
在职情况	学生
学　　校	内蒙古大学
专　　业	软件工程（研究生）

　　自我简介：

爱笑的人运气都不会太差，因为运气差的人总是没有笑容

TA的其他文章

蓝桥杯2019年第十届真题-等差数列-题解(C++代码)
浏览：244

字符逆序-题解(C++代码)
浏览：99

C语言训练-亲密数-题解(C++代码)
浏览：179

你可能喜欢

数据结构-KMP字符串模式匹配算法实现（C++代码）

　　作者: 白鸽　　　　发表时间：2020-03-07 20:39:39 浏览：610　|　评论：0　

原题链接：数据结构-KMP字符串模式匹配算法实现

```cpp
#include <iostream>
using namespace std;
//求kmp中的next数组
void next_f(string p,int n,int *next){
    for(int j=3;j<n;j++){ //遍历存储next数组,next从3开始存储，1,2已经初始化0 和1 了
        if(p[j-1]==p[next[j-1]]){ //如果前一位的字符和前一位的next对应的字符相同，next+1
            next[j]=next[j-1]+1;
        }else{ //如果不等，往前循环，k就是p的下标，初始化一下了
            int k=next[j-1];
            while(1){
                if(k==0){//说明找到第一个都没有找到相同的，next=1
                    next[j]=1;
                    break;
                }else{  //暂时没有循环到最前面，判断一下此时的前一位字符和对应的next的p是否一致
                    if(p[j-1]==p[next[k]]){  //一致，就将此时循环到的p的下标+1赋予next
                        next[j]=next[k]+1;
                        break;
                    }else{  //不一致，就再次初始化p的下标k
                        k=next[k];
                    }
                }
            }
        }
    }
}
int main(){
    string s1,s2;//s1是目标串abcde s2是模式串abc
    for(int i=0;i<3;i++){ //测试3组数据
        cin>>s1>>s2;
        int s2_len=s2.size();
        int s1_len=s1.size();
        int *next=new int[s2_len+1];  //定义next数组，从1开始存储
        next[0]=-1; //为了方便将0的位置赋予-1
        next[1]=0;
        next[2]=1;
        //将s2数组向后移动一位，这里采用字符串的方法，简单一点，因为我必须保证字符也是从1开始存储的，这样求next更好求一点
        string s3='0'+s2;
        //得到next数组
        next_f(s3,s3.size(),next);
       // cout<<"输出模式串的next数组：";
//        for(int i=1;i<s2_len+1;i++){
//            cout<<next[i]<<" ";
//        }
//        cout<<endl;
        int j=0,k=0; //j代表的是模式串s2的下标，k代表的是目标串的下标，都初始化为0
        while(j<s2_len&&k<s1_len){ //当模式串和目标串的下标都小于对应的长度，循环
            if(j==-1||s1[k]==s2[j]){ //这里的j==-1的时候，是开始的时候，如果不匹配，就会走else，这样我的next数组0的时候是-1，j就会变为-1了
                j++;  //当模式串和目标串的字符匹配上之后，各自的下标都自增1
                k++;
            }else{ //这里是当开始没匹配上的时候和匹配失败的时候会走这里，相当于模式串回退
                j=next[j];
            }
        }

if(j>=s2_len){
            cout<<k-s2_len+1<<endl;  //这里题目要求从1开始数，所以+1
        }else{
            cout<<0<<endl;
        }
    }
}

```
具体的next数组的求法，去我简书可以查看：
https://www.jianshu.com/p/5cb298ba0e30

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

白鸽

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

亲和的解法

C语言程序设计教程（第三版）课后习题5.7 （C++代码）

小九九（C语言代码）

C二级辅导-计负均正（C语言代码）

数据结构-KMP字符串模式匹配算法实现（C++代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （Java代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

【明明的随机数】（C++代码）

C语言训练-大、小写问题（C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

字符逆序（C语言代码）

数字游戏（C++代码）

交换Easy （C语言代码）

复数求和（C语言代码）

白鸽

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

亲和的解法

C语言程序设计教程（第三版）课后习题5.7 （C++代码）

小九九 （C语言代码）

C二级辅导-计负均正 （C语言代码）

数据结构-KMP字符串模式匹配算法实现 （C++代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （Java代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

【明明的随机数】 （C++代码）

C语言训练-大、小写问题 （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

字符逆序 （C语言代码）

数字游戏 （C++代码）

交换Easy （C语言代码）

复数求和 （C语言代码）

小九九（C语言代码）

C二级辅导-计负均正（C语言代码）

数据结构-KMP字符串模式匹配算法实现（C++代码）

　　评论区

【明明的随机数】（C++代码）

C语言训练-大、小写问题（C语言代码）

字符逆序（C语言代码）

数字游戏（C++代码）

复数求和（C语言代码）