C++ String Comperison - Why Brute Force alg, works faster than my Knuth–Morris–Pratt alg - I know there must a mistake but I don't know were

Question

I implemented Brute Force alg and Knuth–Morris–Pratt alg and checked how much time it takes for them to complete the task. For a sample of data that I provided it took BF alg 2 seconds to finnish and for the KMP it was 12 seconds. Gap didn't change for other random text samples so there must by some sort of a mistake, cause the difference is to big plus KMP should be faster than BF, no slower.

Brute Force

    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;
    }

Knuth - Morris - Pratt

Don't mind the Queue obj, and the Morrisa_Pratta_Tab_Generator function. I checked it so many times and it works as should. The queue is there out of convenience and it's also definitely not the source of a mistake.

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);
    }

If you have any comments on my code or you know what causes this behaviour, I would be more than happy to read your comment

I did some changes, but none of them made a significant change. The code above is the final product and I don't know what causes it to run so slow

Answer 1

Alright guys, I learned something today. I didn't realize how different Debug_Mode was from Release, I thought that it basically makes the whole thing slower, but the proportions of time performance of each task would be more or less the same. But when I switched to Release the situation turned upside down and now the KMP is a little bit faster than Brute Force, as it should be.

Turn out the algorithm is fine and the fact that I used to run it on Debug_Mode made the difference.

Thanks for the comments and potential solutions