c - 別の配列で部分配列のすべての一致を効率的に見つける方法は?

Question

たとえば、これは私が今それを実装した方法です:

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

size_t *find_matches(char *needle, size_t needleSize, char *haystack, size_t haystackSize, size_t *size) {
    size_t max_matches = 256;
    size_t *matches = malloc(sizeof(size_t) * max_matches);
    int matchCount = 0;
    for(int i = 0; i + needleSize <= haystackSize; i++) {
        bool matched = true;
        for(int j = 0; j < needleSize; j++) {
            if(haystack[i + j] != needle[j]) {
                matched = false;
                break;
            }
        }

        if(matched) {
            matches[matchCount] = i;
            matchCount++;
            if(matchCount == max_matches) {
                break;
            }
        }
    }
    *size = matchCount;
    return matches;
}

int main() {
    char needle[] = {0xed, 0x57, 0x35, 0xe7, 0x00};
    char haystack[] = {0xed, 0x57, 0x35, 0xe7, 0x00, ..., 0xed, 0x57, 0x35, 0xe7, 0x00, ...};
    size_t size;
    size_t *matches = find_matches(needle, sizeof(needle), haystack, sizeof(haystack), &size);

    for(size_t i = 0; i < size; i++) {
        printf("Match %zi: %zi\n", i, matches[i]);
    }

    return 0;
}

これはもっと最適化できませんか？

Answer 1

Rabin–Karp アルゴリズムなど ( Knuth–Morris–Pratt アルゴリズム、Boyer–Moore アルゴリズム)を参照してください。