代码随想录算法训练营第九天|KMP算法略讲与字符串总结-创新互联

KMP算法难度较大，在理解时会有很大的难度，在这里建议大家参考LeetCode28. 实现 strStr()、LeetCode459.重复的子字符串两个题目，并参照代码随想录进一步理解

网址如下：

LeetCode28文章讲解

https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html

LeetCode459文章讲解

https://programmercarl.com/0459.%E9%87%8D%E5%A4%8D%E7%9A%84%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2.html

本文中预先附上KMP算法的相关代码，供大家学习参考

（二刷再战）

void getNext(int* next, const string& s){
    int j = -1;
    next[0] = j;
    for(int i = 1; i< s.size(); i++) { // 注意i从1开始
        while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
            j = next[j]; // 向前回退
        }
        if (s[i] == s[j + 1]) { // 找到相同的前后缀
            j++;
        }
        next[i] = j; // 将j（前缀的长度）赋给next[i]
    }
}

总结篇

字符串的内容相对来说比较简单，总的来看考察题型分为这几种：

• 字符串的基本操作

• 库函数的相关使用

• 双指针法

• 反转系列

• KMP算法的相关应用（重点）

字符串类类型的题目，往往想法比较简单，但是实现起来并不容易，复杂的字符串题目非常考验对代码的掌控能力。

特别注意双指针法是字符串处理的常客。

加油💪！

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧