Алгоритм проверки подстроки в строке

[gogoshik]

Какие существуют алгоритмы поиска подстроки в строке с учетом циклического сдвига и переименования букв? То есть алгоритмы, которые ищут подстроку $S'$ в исходной строке $S$ c точностью до циклического сдвига и переименования букв. Известные алгоритмы этого вроде не учитывают.

[zykov]

gogoshik в сообщении #1541548 писал(а):

Известные алгоритмы
этого вроде не учитывают.

Потому что "с учетом циклического сдвига и переименования букв" - это уже не поиск подстроки, а поиск совпадения с регулярным выражением.
В общем случае строится конечный автомат, который парсит входную строку и ищет совпадение.
Компиляторы регулярных выражений так и делают - генерируют конечный автомат. Если Ваш случай не описывается хорошо стандартными регулярными выражениями, то придётся самому создавать конечный автомат для парсинга.

-- 04.12.2021, 01:02 --

Регулярные выражения - это вариант попроще.
Более сильный вариант - это парсить грамматику.
В стандартном наборе GNU есть утилита Flex. Ей передают описание грамматики языка (наприме C/C++, Java, XML и т.д.) и она создаёт C-код с конечным автоматом для парсинга входного текста на этом языке.

[gogoshik]

zykov, спасибо. А что можно толкового почитать, чтобы решить данную задачу?

[mihaild]

Только автомату и грамматике, по крайней мере если не придумать чего-то хитрого, придется очень многое запоминать.
Циклический сдвиг решается элементарно - ищем $S'$ в строке $SS$. Можно ли с заменой сделать что-то лучше перебора - пока не вижу.

[zykov]

gogoshik
Сильно зависит от того, что именнов Вам надо, что хотите получить в итоге и сколько времени готовы потратить. Зачем это надо - для себя, по работе, по учёбе?
Одно дело, если надо написать один парсер для одной данной "подстроки". Другое дело, если в принципе хотите научится таким вещам.

Самое простое - освоить регулярные выражения.
Посложнее - освоить грамматику (например через flex/bison).
Ещё глубже - научится самому делать такие штуки как flex/bison.

-- 04.12.2021, 03:25 --

"циклическый сдвиг" - какая длина строки? Можно просто взять все сдвиги (количество равно длине строки), сформировать длинное регулярное выражение и передать его компилятору регулярных выражений, чтобы не него переложить грязную работу.
"переименования букв" - что конкретно имеется ввиду? Например если ищут подстроку без учёта регистра, то просто сначала всё переводят в один регистр и там уже ищут. Можно и в более широком смысле это сделать - трансформировать строку так чтобы эквивалентные символы (или даже группы символов) преобразовались в один какой-то символ, и потом в новой строке искать.

[gogoshik]

zykov в сообщении #1541558 писал(а):

"циклическый сдвиг" - какая длина строки?

Строка любой конечной длины.

zykov в сообщении #1541558 писал(а):

"переименования букв" - что конкретно имеется ввиду?

Для примера. Строки "abadcdbc", "abacdcbd" равны. Берем строку "abadcdbc". Переименовываем (d) -> (c) и наоборот. Получаем "abacdcbd".

[zykov]

gogoshik в сообщении #1541648 писал(а):

Переименовываем (d) -> (c) и наоборот

Только 1 раз или сколько угодно раз? Именно пара букв меняется или они могут в любые значения принять (например (d)->(x), (c)->(y) )?
Если любые буквы можно заменить на другие (и если обязательно разные буквы заменяются на разные), то тут вообще не поиск подстроки.
Это поиск паттерна, где условия наложены на равенство символов внутри паттерна.
Например символ №1 равен сиволу №3 и не равен всем другим символам до №8.

А откуда вообще такая задача? Просто самостоятельно для интереса придумали? Или в ВУЗе задали? Или по работе как-то возникла?