• 字符串的匹配——KMP算法的学习


    一、核心:        

            当出现字符串不匹配时,可以记录一部分之前已经匹配的文本内容,利用这些信息避免从头再去做匹配,因此需要一个数组记录已经匹配的文本内容

            对于字符串匹配问题,暴力法也叫朴素求解法是将两个字符串一个一个的比较,时间复杂度为O(mn),但是通过KMP算法,可以将时间复杂度下降到O(m+n)。

    二、next数组

            next数组是一个前缀表,前缀表是用来回退的,它记录了模式串与主串不匹配的时候,模式串应该从哪里开始重新匹配。

    • 前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串;
    • 后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

            前缀表要求相同前后缀的长度。【最长公共前后缀】

            模式串与前缀表对应位置的数字表示:下标 i 之前(包括 i )的字符串中,有多大长度的相同前缀后缀。

      参考代码:

    1. void getNext(vector<int>& nextv, const string& needle) {
    2. nextv[0] = 0;
    3. for(int i=1, j=0; isize(); ++i) {
    4. while(j > 0 && needle[i] != needle[j]) {
    5. //回退
    6. j = nextv[j-1];
    7. }
    8. if(needle[i] == needle[j]) {
    9. nextv[i] = j + 1;
    10. j++;
    11. }
    12. }
    13. }

    三、代码

    问题:找出字符串中第一个不匹配的下标

    1. class Solution {
    2. public:
    3. int strStr(string str, string needle) {
    4. if(needle.size() == 0) return 0;
    5. vector<int> nextv(needle.size(), 0); //定义next数组
    6. getNext(nextv, needle); //计算next数组
    7. for(int i=0,j=0; isize(); ++i) {
    8. while(j > 0 && str[i] != needle[j]) {
    9. j = nextv[j - 1];
    10. }
    11. if(str[i] == needle[j]) {
    12. j++;
    13. }
    14. if(j == needle.size()) {
    15. return (i - j + 1);
    16. }
    17. }
    18. return -1;
    19. }
    20. };

    问题2:重复叠加字符串匹配

            思路:首先找到b串第一次出现的位置;然后计算a串重复的次数。

            解释:对于a串重复的次数部分,当确定了b串的第一次出现的位置index后,如果a串的大小减去index后依然比b串的大小大,那么a串完全覆盖b串,此时返回1;如果a串剩余的部分比b串小,那么将重复n次的a串根据index斩头去尾然后除以a串的大小,即b串内部需要a串重复的次数,进而加上头与尾超出的部分两次,即最终的n。

    1. class Solution {
    2. public:
    3. int KMP(string a, string b) {
    4. //if(b.size() == 0) return 0;
    5. vector<int> nextv(b.size(), 0);
    6. for(int i=1, j=0; isize(); ++i) {
    7. while(j > 0 && b[i] != b[j]) {//b[i] != b[j]
    8. j = nextv[j - 1];
    9. }
    10. if(b[i] == b[j]) {
    11. nextv[i] = j + 1;
    12. j++;
    13. }
    14. }
    15. for(int i=0, j=0; isize()+b.size(); ++i) {
    16. while(j > 0 && a[i%a.size()] != b[j]) {//a[i%a.size()]
    17. j = nextv[j - 1];
    18. }
    19. if(a[i%a.size()] == b[j]) {
    20. j++;
    21. }
    22. if(j == b.size()) {
    23. return i-j+1;
    24. }
    25. }
    26. return -1;
    27. }
    28. int repeatedStringMatch(string a, string b) {
    29. //1.获取第一次出现的位置
    30. int res = KMP(a, b);
    31. //2.计算a串重复次数
    32. if(res != -1) {
    33. if(a.size() - res >= b.size()) {
    34. res = 1;
    35. }
    36. else {
    37. res = 2 + (b.size() - a.size() + res - 1)/a.size();
    38. }
    39. }
    40. return res;
    41. }
    42. };
  • 相关阅读:
    红旗系统Asianux 8.1常用命令(配置jdk、mysql、redis、RabbitMQ等等)
    技术篇——废水除铊、除铊吸附树脂技术
    微信好友消息自动回复,让你轻松应对好友咨询
    【Java】微服务——微服务介绍和Eureka注册中心
    gitea的git库备份与恢复
    微服务篇-B 深入理解SOA框架(Dubbo)_III SpringBoot整合Dubbo(学习总结)
    【微服务】微服务常见概念
    越折腾越好用的 3 款开源 APP
    Bit, byte, KB, GB, MG
    jvm虚拟机浅谈(二)
  • 原文地址:https://blog.csdn.net/xiaoyeren_ITRoad/article/details/133975180