I异乡人l 2021-08-15 12:56 采纳率: 100%
浏览 48
已结题

自己写的KMP算法,出了点问题


#include<iostream>
#include<string>
using namespace std;

int* get_next(string needle)
{
    int* next = new int[needle.size()];
    int i = 0, j = -1;
    next[0] = -1;
    while (i < needle.size() - 1)
    {
        if (j == -1 || needle[i] == needle[j])
        {
            ++i, ++j;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
    return next;
}

int KMP(string needle, string haystack)
{
    int* next = get_next(needle);
    int i = 0, j = 0;
    while (i < haystack.size() && j < needle.size())
    {
        if (j == -1 || haystack[i] == needle[j])
        {
            ++i, ++j;
        }
        else
        {
            j = next[j];
        }
    }
    if (j == needle.size())
    {
        return i - j;
    }
    return -2;
}

int main()
{
    string haystack = "abcacbcdf";
    string needle = "acb";
    cout << KMP(haystack, needle);
    return 0;
}

该程序最终返回的是-2,但是按照KMP算法应当返回3,我进行调试发现i = 1, j = -1 时就跳出了while,有点搞不明白为什么,向各位请教一下原因

  • 写回答

1条回答 默认 最新

  • qzjhjxj 2021-08-15 13:41
    关注

    C++中string类size() 函数的返回值是无符号数,所以判断的地方需强制类型转换下,供参考:

    #include<iostream>
    #include<string>
    using namespace std;
    int* get_next(string needle)
    {
        int* next = new int[needle.size()];
        int i = 0, j = -1;
        next[0] = -1;
        while (i < (int)needle.size() - 1)
        {
            if (j == -1 || needle[i] == needle[j])
            {
                ++i, ++j;
                next[i] = j;
            }
            else
            {
                j = next[j];
            }
        }
        return next;
    }
    int KMP(string needle, string haystack)
    {
        int* next = get_next(needle);
        int i = 0, j = 0;
        while (i < (int)haystack.size() && j < (int)needle.size())
        {
            if (j == -1 || haystack[i] == needle[j])
            {
                ++i, ++j;
            }
            else
            {
                j = next[j];
            }
        }
        if (j == (int)needle.size())
        {
            return i - j;
        }
        return -2;
    }
    int main()
    {
        string haystack = "abcacbcdf";
        string needle = "acb";
        cout << KMP(haystack, needle);
        return 0;
    }
    
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 8月23日
  • 已采纳回答 8月15日
  • 创建了问题 8月15日

悬赏问题

  • ¥15 安装gcc遇到的问题
  • ¥15 求购HI3519AV100开发板
  • ¥15 请问1553 RT怎么测试,没有BC有方法吗
  • ¥100 业务编程如何选择学习方向和内容?
  • ¥15 wamp3.3.5安装完成后图标正常显示绿色,鼠标左右键点击图标均无反应。求解决方法。
  • ¥15 鼠标点击的这条记录了什么?
  • ¥15 在写pid调速的程序时,电机始终维持最大速度
  • ¥15 【有偿】调用DXGI截图初始化失败,提示0xf 887a0004
  • ¥15 请问如何查看手机root记录?
  • ¥15 商城小程序订单号重复