2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Алгоритм проверки подстроки в строке
Сообщение04.12.2021, 00:46 


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

 Профиль  
                  
 
 Re: Алгоритм проверки подстроки в строке
Сообщение04.12.2021, 00:57 


18/09/21
1676
gogoshik в сообщении #1541548 писал(а):
Известные алгоритмы
этого вроде не учитывают.
Потому что "с учетом циклического сдвига и переименования букв" - это уже не поиск подстроки, а поиск совпадения с регулярным выражением.
В общем случае строится конечный автомат, который парсит входную строку и ищет совпадение.
Компиляторы регулярных выражений так и делают - генерируют конечный автомат. Если Ваш случай не описывается хорошо стандартными регулярными выражениями, то придётся самому создавать конечный автомат для парсинга.

-- 04.12.2021, 01:02 --

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

 Профиль  
                  
 
 Re: Алгоритм проверки подстроки в строке
Сообщение04.12.2021, 01:09 


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

 Профиль  
                  
 
 Re: Алгоритм проверки подстроки в строке
Сообщение04.12.2021, 01:16 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Алгоритм проверки подстроки в строке
Сообщение04.12.2021, 02:48 


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

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

-- 04.12.2021, 03:25 --

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

 Профиль  
                  
 
 Re: Алгоритм проверки подстроки в строке
Сообщение04.12.2021, 22:57 


11/12/16
403
сБп
zykov в сообщении #1541558 писал(а):
"циклическый сдвиг" - какая длина строки?
Строка любой конечной длины.
zykov в сообщении #1541558 писал(а):
"переименования букв" - что конкретно имеется ввиду?
Для примера. Строки "abadcdbc", "abacdcbd" равны. Берем строку "abadcdbc". Переименовываем (d) -> (c) и наоборот. Получаем "abacdcbd".

 Профиль  
                  
 
 Re: Алгоритм проверки подстроки в строке
Сообщение04.12.2021, 23:23 


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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group