Задача 16. Необходимо найти максимальную подстроку слова word, которое является подсловом слова из языка регулярного выражения. Решение реализуется динамикой по регулярному выражению. По мере раскрытия регулярного выражения будем держать в стеке описание всех подстрок строки word. Описание заключается в следующем: для каждой подстроки в массиве держим 4 флага - является ли подстрока полным словом в языке, является ли суффиксом какого-то слова в языке, является ли префиксом какого-то слова в языке, является ли подсловом слова из языка. Как насчитывать такие массивы?
-
При объединении языков(L+R)
Здесь нужно просто сделать поэлементное или(|) двух массивов с флагами
-
При конкатенации языков(L.R)
a) Если подстрока является элементом нового языка, полученного конкатенацией, то она является конкатенацией двух полных слов из языков.
б) Если подстрока является префиксом слова нового языка, то она может быть получена как префикс L или как конкатенация полного слова из L и префикса слова из R.
в) Если подстрока является суффиксом слова нового языка, то она может быть получена либо как суффикс слова из R, либо как конкатенация суффикса из L и полного слова из R.
г) Если подстрока является подсловом слова нового языка, то она может быть получена либо как подслово из R, либо как подслово из L, либо как конкатенация суффикса из L и префикса из R.
Таким образом, по массиву с флагами двух языков L и R можно насчитать новый.
-
При замыкании (L*)
а) Если подстрока является элементом нового языка, то она является элементом L или конкатенацией полных слов из L.
б) Если строка является префиксом слова нового языка, то она представима либо как префикс слова из L, либо как конкатенация некоторого количества полных слов из L и префикса какого-то слова из L.
в) Если строка является суффиксом слова нового языка, то она представима либо как суффикс слова из R, либо как конкатенация суффикса слова из L и некоторого количества полных слов из R.
г) Если строка является подсловом слова нового языка, то она представима как конкатенация суффикса слова из L, слова из L* и префикса слова из L.
Таким образом, снова можно насчитывать массив для нового языка. (на будущее заметим, что конкатенация полных слов языка L - это слово из L*, префикс слова из L - это префикс слова из L*, суффикс слова из L - это суффикс слова из L*)
Технические моменты
Для обработки строки заведем класс SubstrAnalyser, который работает с подстроками строки. Массив подстрок представляет из себя следующее: нулевой элемент - пустая строка, далее все подстркои, расположенные по возрастанию длины, а если длины равны, то по возрастанию индекса вхождения первого символа в строку word. (пример для abc: E, a, b, c, ab, bc, abc). Чтобы не держать массив подстрок, заведем массив length_index. length_index[l] - индекс первого вхождения подстроки длины l в массив подстрок, описанный выше. Тогда, если мы знаем длину строки l и индекс ее первого элемента i, то индекс непустой подстроки в массиве подстрок в точности length_index[l] + i. Тогда для обработки регулярного выражения, храним в стеке массивы с флагами entry_arr(массив вхождений), entry_arr[i] содержит флаги для подстроки с индексом i.
При конкатенации делаем следующее: перебираем длины подстрок l, для каждой длины перебираем индексы i первых букв подстрок. Итак, имеем строку длины l с началом в i, осталось перебрать все подстроки, которые "продолжают" нашу строку, то есть те, у которых начало в i + l. Для этого достаточно перебрать все возможные длины k продолжающей строки. В ходе перебора будем получать строки длины l + k, для которых флаги заполняются по правилам пункта 2.
При замыкании первым делом массив вхождений подстрок нового языка L* проинициализируем массивом вхождений порождающего языка L а также отметим пустое слово как полное подслово языка. Далее организуем перебор, как для конкатенации: для нового подслова длины l + k флаги заполняются. Тогда для слов длины меньше чем l и k в массиве вхождений флаги заполнены верно, значит и для нового подслова мы можем по правилам пункта 3 заполнить флаги.