Как можно выполнить поиск в обратном порядке для последней подходящей подстроки при запрете перекрытий?
Я работаю со Swift, и я написал функцию, чтобы найти Range<Index> первой подпоследовательности данного Collection который соответствует данной коллекции шаблонов. (Возвращается nil если совпадений не найдено.) Я сделал вариант, который возвращает последнее совпадение для BidirectionalCollections. Сейчас я пытаюсь сделать Sequence/Collection который возвращает диапазоны индекса всех совпадений. У него есть управляющий параметр, разрешающий ли перекрывающиеся совпадения.
Поиск вперед легко. Позвоните в мою функцию поиска, чтобы найти первое совпадение. Чтобы найти последующие совпадения, увеличьте на единицу начальный (разрешающий перекрытие) или конечный (запрещающий перекрытие) маркер последнего диапазона сопоставления, а затем снова вызовите функцию поиска.
Если вы разрешите дублирование, я чувствую, что поиск в обратном направлении тоже прост. Вызовите функцию обратного поиска, чтобы найти последнее (то есть первое обратное) совпадение. Для анти-последующих совпадений уменьшите конечный маркер на единицу, затем снова вызовите функцию поиска.
Проблема заключается в обратном поиске с одновременным запретом наложений. Перекрытия могут быть обнаружены только через поиск вперед! Например:
"121212124"
и я ищу "1212". Возвращаясь назад, я нахожу первое со смещением 4. Но есть совпадение со совпадением со смещением 2. Второе обратное совпадение имеет перекрытие со совпадением со смещением 0. Нет предыдущих перекрытий с совпадением со смещением 0 (потому что это против начала строки), поэтому смещение 0 совпадает. Совпадение по смещению-0 отменяет совпадение по смещению-2 из-за перекрытия. Поэтому совпадение по смещению-4 является официальным последним совпадением, поскольку никакое действительное предыдущее совпадение не перекрывается с ним (поскольку все совпадения, которые перекрываются с ним, были признаны недействительными).
Я чувствую, что есть (рекурсивный) алгоритм, который может понять это, но я спрашиваю здесь, если кто-то уже сделал это, как в известной книге или что-то.