如何有效地找到另一个数组中的子数组的所有匹配？

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 algorithm等（Knuth–Morris–Pratt algorithm,Boyer–Moore algorithm）。