有没有大神能不能帮忙看下啊这个c++KMP算法的代码实现

也是初学, 把楼主的代码改了改了改, 简单测试通过, 没有进行详细测试.

代码如下:

//======================
//KMP算法
//======================
#include 
#include 
#include 
#include 
#include  // for strlen

using namespace std;

//main 返回 int
int main()
{
    char S[80],T[80];

    void getnext(char* T ,int* next ); //getnext函数声明

    cout<<"请输入主串 S:"<    cin>>S;

    cout<<"请输入子串 T:"<    cin>>T;

    int i=0,j=0;
    int* next=new int[strlen(T)]; //为next开辟了空间，而且形参是指针型，可以使用其中的内容
    getnext(T,next);
    int k = 0;
#if 0
    // 调试next数组
    for(k = 0; k < strlen(T); ++k) {
        cout << next[k] << " ";
    }
    cout << "\n";
#endif
    // 这个循环比较好理解, 注意边界条件, 我也没有全面测试
    while(i        if(S[i]==T[j]) {
            ++i;++j;
        } else {
            // 不匹配i也要往前加, kmp中i只加不退
            ++i;
            j=next[j-1]+1;
        }
    }
    if(j>=strlen(T)-1) {
        cout<    } else {
        cout<<"匹配失败"<    }

    return 0;
}
//=========================
void getnext(char* T,int* next)
{
    int j=1,k=0;
    next[0]=0;
    // 注意k的含义, k是字符串T[0~j-1]公共前缀和后缀的长度
    while(j        if(T[j]==T[k]){
            ++k;
            next[j]=k;
            ++j;
        } else {
            if(k != 0) {
                // 这里有点不好理解, 考虑AACAAA 中最后一个A处的情况
                // 不匹配公共前缀时, 要在公共前缀中向前递推, 找更短的公共前缀
                // 注意只是把k减小了, j的值没有变
                k=next[k-1]; //总是求k；
            } else {
                next[j] = 0;
                ++j;
            }
        }
    }
}

参考geeksforgeeks页面:

网页链接

不懂的我们再交流下, 我会尽力解答.