Вот еще одна идея. Работает ли это для вас, зависит от того, сколько данных вы обрабатываете, сколько памяти вы можете использовать и какие типы обнаруженных шаблонов оказываются полезными для ваших целей.
Имея в виду все эти квалификации, вы можете попробовать использовать суффиксное дерево или суффиксный массив . Особенно для деревьев суффиксов существуют алгоритмы, которые позволяют вам постоянно обновлять дерево при добавлении символов к тексту (так называемое построение дерева суффиксов ), в особенности алгоритм Укконена. Это может особенно хорошо работать с использованием потоков данных (в отличие от полностью определенного входного текста фиксированной длины).
Дерево суффиксов (и, аналогично, массив суффиксов) представляет все суффиксы (в смысле концов строк, а не лингвистических суффиксов) текста. Как таковой, он особенно подходит для (а) проверки, является ли любая заданная строка подстрокой текста, и (б) для обнаружения повторных подстрок в тексте. С некоторыми изменениями в нужных местах, он может быть использован для обнаружения повторяющихся подстрок с небольшими изменениями (как ваш пример шаблона, который повторяется с одним символом, обмененным в середине).
Для подробного ознакомления с этими структурами данных и если у вас есть доступ к университетской библиотеке или есть деньги, Введение Дана Гасфилда в алгоритмы для строк, деревьев и последовательностей будет очень полезно. Но в SO также есть ряд вопросов и ответов, связанных с этим.
Если, после некоторого прочтения, вы думаете, что стоит попробовать, я мог бы более подробно рассказать о том, как я думаю, что деревья суффиксов могут использоваться для ваших целей, в ответ на новый вопрос, конкретно об использовании этих алгоритмов для повторного обнаружение шаблона.