find pattern in string

find-pattern.c

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

/**
 * Hamming Weight
 * Code from stackoverflow:
 * @see https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer
 */
uint8_t numberOfSetBits(uint32_t i)
{
     i = i - ((i >> 1) & 0x55555555);
     i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
     return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

uint32_t strBitDiff(uint32_t *str1, uint32_t *str2, uint32_t len)
{
    uint32_t sum = 0;
    for(uint32_t i = 0; i < len; i++) {
        sum += numberOfSetBits(str1[i] ^ str2[i]);
    }
    return sum;
}

uint32_t findPatterntInString(uint32_t *string, uint32_t string_length, uint32_t *pattern, uint32_t pattern_length, uint32_t * diff)
{
    uint32_t right = string_length - pattern_length;
    *diff = 32 * pattern_length + 1;
    uint32_t index = 0, curDiff;
    for (uint32_t i = 0; i <= right; i++) {
        curDiff = strBitDiff(string + i, pattern, pattern_length);
        if (curDiff < *diff) {
            *diff = curDiff;
            index = i;
        }
    }
    return index;
}

int main()
{
    uint32_t string_length, pattern_length;
    uint32_t *string, *pattern;
    scanf("%u%u", &string_length, &pattern_length);
    string = malloc(4 * string_length);
    pattern = malloc(4 * pattern_length);
    for(uint32_t i = 0; i < string_length; i++) {
        scanf("%u", string + i);
    }
    for(uint32_t i = 0; i < pattern_length; i++) {
        scanf("%u", pattern + i);
    }
    uint32_t diff, index;
    index = findPatterntInString(string, string_length, pattern, pattern_length, &diff);
    printf("Pattern found in string[%u] with %u bits (%f%%) mismatch\n", index, diff, 100.0 * diff/(32*pattern_length));
    return 0;
}