algorithm - 为什么此 KMP 代码显示运行时错误？

Question

从函数返回一个向量会产生什么问题吗？还是只是一些基本的语法问题？

这只是CLRS中的示例代码. computePrefix 函数计算给定模式的正确前缀的值，并匹配主函数中的值。

获取 SIGSEGV 错误更准确。您的建议真的很有帮助。

谢谢。

#include <bits/stdc++.h>

using namespace std;

int main()
{
    string text, pattern;
    vector<int> computePrefixFunction(string p);
    cin >> text;
    cin >> pattern;
    int n = text.length();
    int m = pattern.length();
    vector<int> pi = computePrefixFunction(pattern); 
    int q = -1;
    for(int i = 0; i < n; ++i)
    {
        while(q > -1 && pattern[q+1] != text[i])
            q = pi[q];
        if(pattern[q+1] == text[i])
            q = q + 1;
        if(q == (m-1))
        {
            cout << "Pattern occurs from position: " << q - m + 1 << '\n';
            q = pi[q];
        }
    }
    return 0;
}

vector<int> computePrefixFunction(string p)
{
    int m = p.length();
    vector<int> pi;
    pi[0] = -1;
    int k = -1;
    for(int q = 0; q < m; ++q)
    {
        while(k > -1 && p[k+1] != p[q])
            k = pi[k];
        if(p[k+1] == p[q])
            k = k + 1;
        pi[q] = k;
    }
    return pi;
}

Answer 1

要使用vector，请执行push_back 以向其添加元素。如果您只是像在 computePrefixFunction 的第二行中那样初始化它而没有大小，则尝试访问 pi[0] 或 pi[q] 会给你一个运行时错误。相反，执行 pi.push_back(value)。