Aurora

void get_next(vector<int>& next,string& t)
{
    auto len = (int)t.size();
    int i=-1, j=0;
    //i 为前缀 j 为后缀 , 每次也就是计算j的前缀和后缀相等位数,所以循环以j结束为条件
    next[0]=-1;
    //初始化,我的理解是kmp的第一个if 用来根据以求得的next[i]来计算下一个next[j],第二个else 
    // 用来进行回溯,找到前缀和后缀相同的情况,next[0]=-1,则是为它的回溯设定了终止条件
    while (j<len)
    {
        if (i==-1 || t[i]==t[j])
        {
            //计算j的next
            i++;
            j++;
            next[j]=i;
        }
        else
            i=next[i];
        //回溯
    }
}
bool kmp(string& str,string& t,int& pos)
{
    int i=0,j=0;
    auto len1 = (int)str.size();
    auto len2 = (int)t.size();

vector<int> next(len2);
    get_next(next,t);

while (i<len1 && j<len2)
    {
        if (j==-1 || str[i]==t[j])
        {
            i++;
            j++;
        }
        else
            j = next[j];
        //子串回溯,主串不变
    }
    if (j==len2)
    {
        pos = i-j+1;
        return true;
    }
    return false;
}

int main()
{
    string str;
    string t;
    while (cin >> str >> t)
    {
        int pos;
        if (kmp(str,t,pos))
            cout << pos << std::endl;
        else
            cout << 0 << std::endl;
    }
    return 0;
}
```

0.0分

0 人评分

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

Aurora

TA的其他文章

你可能喜欢

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

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

不容易系列（C语言代码）

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

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

1691: 数据结构-KMP字符串模式匹配算法实现

评论区

精彩推荐

逆反的01串（C++代码）（依旧推荐switch）

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

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

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

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

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

妹子杀手的故事（C语言代码）

时间转换（C语言代码）

矩阵转置（C语言代码）

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

Aurora

TA的其他文章

你可能喜欢

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）

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

不容易系列 （C语言代码）

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

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

1691: 数据结构-KMP字符串模式匹配算法实现

评论区

精彩推荐

逆反的01串 （C++代码）（依旧推荐switch）

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

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

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

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

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

妹子杀手的故事 （C语言代码）

时间转换 （C语言代码）

矩阵转置 （C语言代码）

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

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

不容易系列（C语言代码）

　　评论区

逆反的01串（C++代码）（依旧推荐switch）

妹子杀手的故事（C语言代码）

时间转换（C语言代码）

矩阵转置（C语言代码）