C++ 中的 KMP 算法实现给出运行时错误

Question

我已经用 C++ 实现了 Knuth-Morris-Pratt 算法。实施似乎是正确的，但我遇到了一个我似乎无法弄清楚的运行时错误。在这方面需要帮助。

#include <iostream>
#include <cstring>
#include <string>

using namespace std;

int* PrefixFunction(string pattern) {
    int m = pattern.length() ;
    int PrefixTable[m] ;
    PrefixTable[0] = 0 ;
    int k = 0 ;

    for(int q = 1; q<m; q++) {
        while(k>0&&pattern[k]!=pattern[q]) {
            k = PrefixTable[k] ;
        }
        if(pattern[k]==pattern[q]){
            k = k + 1 ;
        }
        PrefixTable[q] = k ;
    }

    return PrefixTable ;
}

void KMP(string text,string pattern) {
    int* PrefixTable = PrefixFunction(pattern) ;
    int n = text.length() ;
    int m = pattern.length() ;
    int q = 0 ; //characters matched

    for(int i=0;i<n;i++) {
        while(q>0&&pattern[q]!=text[i]) {
            q = PrefixTable[q] ;
        }
        if(pattern[q]==text[i]) {
            q = q + 1 ;
        }
        if(q==m) {
            cout<<"found : "<<i-m ;
            q = PrefixTable[q] ;
        }
    }

}

int main() {
    string text, pattern ;

    cout<<"Enter the text : " ;
    cin>>text ;

    cout<<"Enter the pattern : " ;
    cin>>pattern ;

    KMP(text,pattern) ;
    return 0 ;
}

程序要求输入后出现运行时错误。需要指导。

Answer 1

你 return 一个局部变量，PrefixTable。但是一旦你离开你的函数，这个变量的堆栈 space 就会被释放。您应该传入它或使用 new.

分配它

一个吹毛求疵的评论：如果你的类只以大写开头，函数、变量等以小写开头，那么你的程序对许多人来说会更具可读性。

Answer 2

PrefixFunction 返回一个指向局部变量的指针，PrefixTable，自动存储。
当函数returns时，数组不复存在，解引用指针使程序未定义。

（在这种情况下可能发生的具体情况是，对 length() 的调用会将它们自己的自动变量放在数组曾经所在的位置，并且当您使用这些 "values" 作为程序的索引时繁荣。）

考虑使用 std::vector<int> 而不是数组。

std::vector<int> PrefixFunction(string pattern) {
    int m = pattern.length();
    std::vector<int> PrefixTable(m);
    // As before...

如果你不能使用std::vector，你可以使用动态分配（记得之后释放内存），或者你可以将table作为参数传递给函数而不是返回它：

void PrefixFunction(string pattern, int* PrefixTable)

// ...

void KMP(string text,string pattern) {
    int m = pattern.length();
    int PrefixTable[m];
    PrefixFunction(pattern, PrefixTable);
    // ...

C++ 中的 KMP 算法实现给出运行时错误

KMP Algorithm Implementation in C++ gives Runtime Error

c++

algorithm

runtime