Я ищу (космическую) эффективную реализацию алгоритма LCS для использования в программе на C ++. Входами являются две последовательности произвольного доступа целых чисел.
В настоящее время я использую подход динамического программирования со страницы Википедии о LCS. Однако, это имеет O (mn) поведение в памяти и времени и умирает от меня с ошибками нехватки памяти для больших входов.
Я читал об алгоритме Хиршберга, который значительно улучшает использование памяти, Ханта-Шимански, Масека и Патерсона. Поскольку реализовать их нетривиально, я бы предпочел опробовать их на моих данных в существующей реализации. Кто-нибудь знает о такой библиотеке? Я полагаю, поскольку текстовые инструменты сравнения довольно распространены, вокруг должны быть библиотеки с открытым исходным кодом?