博客

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

int *GetNext(char *s, int *next)
{
    int i = 0;
    int j = -1;
    next[0] = -1;
    while (i < strlen(s))
    {
        //判断j == -1 || s[i] == s[j]
        if (j == -1 || s[i] == s[j])
        {
            next[++i] = ++j;
        }
        else
        {
            //回溯
            j = next[j];
        }
    }
    return next;
}

int KMP(char *S, char *T, int *next)
{
    int i = 0;
    int j = 0;
    int s_len = strlen(S);
    int t_len = strlen(T);
    while (i < s_len && j < t_len)
    {
        if (j == -1 || S[i] == T[j])
        {
            ++i;
            ++j;
        }
        else
        {
            j = next[j];
        }
    }
    //判断T字符串是否结束
    if (j == strlen(T))
    {
        return i - strlen(T);
    }
    else
    {
        return -1;
    }
}
int main()
{
    char s[10] = "abbadbasa";
    char t[4] = "adb";
    int next[4] = {0};
    int num = KMP(s, t, GetNext(t, next));
    cout << num << endl;
    return 0;
}

输出结果为3，验证正确

遇到的问题：

写KMP算法的时候，遇到这一段代码：

while (i < s_len && j < t_len)
    {
        if (j == -1 || S[i] == T[j])
        {
            ++i;
            ++j;
        }
        else
        {
            j = next[j];
        }
    }

如果写成这样

while (i < strlen(S) && j < strlen(T))
    {
        if (j == -1 || S[i] == T[j])
        {
            ++i;
            ++j;
        }
        else
        {
            j = next[j];
        }
    }

编译器得出的结果一直不对，因此花费了好长时间来找原因。

i = 0

j = 0

i = 1

j = 1

i = 1

j = 0

-1

最终才知道 strlen()函数的返回值是unsigned int 类型的值，当j = -1的时候，由于编译器发现类型不匹配，因此退出循环。

由此，以后写循环条件的时候 一定要注意类型匹配问题。。。