C++ Алгоритм для поиска определенной последовательности целых чисел

Question

Предположим, что у меня есть определенная последовательность целых чисел. Его нельзя сортировать. Там нет распределения вероятности частоты целых чисел:

S = [12 65 37 52 45 63]. 

Теперь, скажем, у меня есть группа из 100 различных последовательностей, называемого D, что я должен искать через. D не должен сортироваться в любом случае. В D. Не существует распределения вероятностей в D. Каждая последовательность в D имеет ту же длину, что и S.

Существует ли алгоритм, который быстро выполняет поиск по D точно для конкретной последовательности S?

Answer 1

Вы должны предварительно обработать D. Попробуйте вставить все последовательности D в prefix tree.

Таким образом, вы можете проверить, является ли последовательность S длины n в D по времени O(n), что является оптимальным, потому что по крайней мере вам нужно прочитать S один раз.