Поиск подстроки в другой строке

Question

Как бы я написал эффективный алгоритм для поиска подмножества целых чисел в другом массиве в C?Например:

unsigned a[] = {42, 72, 61, 1023, 84, 42, 42, 193, 302, 72};
unsigned long al = 10;
unsigned b[] = {61, 1023, 84};
unsigned long bl = 3;

Я пробовал использовать метод грубой силы, циклически повторяя a, а затем повторяя b, если a[n] равно b[0], но затем возвращаясь назад, если совпадениетерпит неудачу на полпути.Кажется, это лучшее, что я могу придумать, но я уверен, что должен быть более быстрый путь.

Answer 1

Существует несколько известных, эффективных алгоритмов поиска строк , и все они будут работать для этой цели. На самом деле нет никакой разницы между массивом целых чисел и массивом целых чисел, каждое из которых было присвоено символьным представлениям, если вы ищете подпоследовательность.

Если ваша проблема действительно мала по сравнению с тем, что вы опубликовали, вероятно, не стоит использовать ничего, кроме грубой силы, но я предполагаю, что это всего лишь игрушечный пример того, что вы хотите сделать.