Implementation of the Wikipedia-version of the KMP string matching algorithm in C

kmp.cpp

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main(int ArgCount, char **Args)
{
    char *Pattern = "ababcabab";
    char *Text = "abababcbababcababcab";
    
    size_t PatternLength = strlen(Pattern);
    size_t PrefixTableSize = sizeof(int) * (PatternLength + 1);
    int *PrefixTable = (int *)malloc(PrefixTableSize);
    memset(PrefixTable, 0, PrefixTableSize);
    
    // NOTE(johannes): Build the prefix table.
    int PrefixLength = -1;
    PrefixTable[0] = PrefixLength;
    for(int PatternCharIndex = 0;
        PatternCharIndex < PatternLength;
        ++PatternCharIndex)
    {
        while((PrefixLength >= 0) && (Pattern[PrefixLength] != Pattern[PatternCharIndex]))
        {
            PrefixLength = PrefixTable[PrefixLength];
        }
        
        ++PrefixLength;
        PrefixTable[PatternCharIndex + 1] = PrefixLength;
    }
    
    printf("\"%s\" matching \"%s\":\n", Text, Pattern);
    
    // NOTE(johannes): Perform the string matching algorithm
    size_t TextLength = strlen(Text);
    for(int CharIndex = 0, PatternIndex = 0;
        CharIndex < TextLength;
        ++CharIndex)
    {
        while((PatternIndex >= 0) && (Text[CharIndex] != Pattern[PatternIndex]))
        {
            PatternIndex = PrefixTable[PatternIndex];
        }
        
        ++PatternIndex;
        if(PatternIndex == PatternLength)
        {
            int MatchIndex = (CharIndex - PatternLength + 1);
            printf("%d: \"%.*s\"\n", MatchIndex, (int)PatternLength, Text + MatchIndex);
            PatternIndex = PrefixTable[PatternIndex];
        }
    }
    
    return(0);
}