C++字符串匹配：暴力算法为何比KMP算法更快？求问题排查

我实现了暴力匹配（Brute Force）算法和Knuth–Morris–Pratt（KMP）算法，测试执行耗时后发现：暴力算法耗时2秒，KMP算法却需要12秒；更换其他随机文本测试，两者的耗时差距依然没有改变。按理论KMP算法应快于暴力匹配，因此推测我的KMP实现存在错误，现寻求帮助排查性能低下的原因。

暴力算法代码 #

bool Does_full_pattern_match(const string& full_tekst, const string& pattern, const int& index_of_first_match)
{
    if (full_tekst != "" && pattern != "" && index_of_first_match >= 0)
    {
        for (int i = 0; i < (int)pattern.length(); i++)
        {
            if (pattern[i] != full_tekst[index_of_first_match + i]) return false;
        }
        return true;
    }
    else return false;
}
int* Brute_Force_Approach_returns_table_of_index(const string& full_tekst, const string& pattern, int& size)
{
    if (pattern != "")
    {
        Queue<int> obj;
                
        int length = full_tekst.length();
        
        for (int i = 0; i < length; i++)
        {
            if ((full_tekst[i] == pattern[0]) && Does_full_pattern_match(full_tekst, pattern, i))
            {                   
                obj.Enque(i);
            }
        }       

        return obj.Return_Tab(size);
    }
    else return nullptr;
}

KMP算法代码 #

注：已确认Queue对象和Morrisa_Pratta_Tab_Generator函数无问题，并非性能瓶颈。

int Return_Index_Of_Missmatch(const string& full_tekst, const string& pattern, const int& limit, const int& pattern_size, const int& index_in_tekst)
{
    if (full_tekst == "" || pattern == "" || index_in_tekst < 0) return -2;
    else
    {       
        for (int i = 0; i < pattern_size && index_in_tekst + i < limit; i++)
        {
            if (pattern[i] != full_tekst[index_in_tekst + i]) return i;
        }
        return -1;
    }
}
int* KMP(const string& full_tekst, const string& pattern, int& size_of_returned_tab)
{
    
    int length = (int)full_tekst.length();
    int pattern_size = (int)pattern.length();
        
    int size = 0;
    int* prefix_table = Morrisa_Pratta_Tab_Generator(pattern, size);
    for (int i = 0; i < size; i++) prefix_table[i]++;   
    
    Queue<int> found_match_index;
    
    int result;
    for (int i = 0; i < length; )
    {
        result = Return_Index_Of_Missmatch(full_tekst, pattern, length, pattern_size, i);

        if (0 <= result)
        {
            i += prefix_table[result];
        }
        else if (result == -1) // found match
        {
            found_match_index.Enque(i);
            i += pattern_size;
        }
    }
    
    return found_match_index.Return_Tab(size_of_returned_tab);
}

内容的提问来源于stack exchange，提问作者Enigma24