Как мне эффективно искать определенную последовательность в массиве?

Question

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

В настоящее время я последовательно просматриваю большой массив для первого элемента в последовательности поиска, а затем проверяю каждый элемент до тех пор, пока не произойдет сбой или полное совпадение. Это обеспечивает 100% точность, но не очень быстро с большими массивами.

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

Answer 1

Как насчет использования алгоритма Бойера-Мура ? Это довольно просто и понятно, и может значительно увеличить практическую скорость, особенно если ваша целевая последовательность довольно длинная. Он предназначен для поиска строк, но это, конечно же, массив определенного типа.

Answer 2

Если вам нужно искать много паттернов в одной и той же последовательности, вы можете использовать суффиксные массивы

Если вам нужно искать один паттерн, вы можете немного улучшить грубую силу с помощьюБойер-Мур или Кнут-Моррис-Пратт

Answer 3

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

При этом вы можете оптимизировать прием или отклонение кандидатов, используя метод, предложенный Янне.