Поиск нескольких подстрок в строке
Подскажите, пожалуйста, эффективный алгоритм поиска подстрок в строке, такой чтобы в строке он искал подстроки a1, a2, a3, .. ax, b1, b2, b3. bx, c1. z1, z2, z3. zx, такие, что в сумме все подстроки образуют строку. При этом строка задана, а подстроки - нет, но при этом известно, что каждая подстрока a_i, b_i. i=1..x входит в список A, B. , то есть строка определена, а подстроки должен определить сам алгоритм?
Re: Поиск нескольких подстрок в строке
А что мешает собрать регулярное выражение
(a1 | a2 | . | ax) (b1| b2| . |bx) . (z1|. zx)
Re: Поиск нескольких подстрок в строке
x неизвестно, кроме того, количество типов подстрок тоже неизвестно. То есть нужно определить количество самих подстрок, типов подстрок и дать им значения, чтобы в сумме они давали строку.
Re: Поиск нескольких подстрок в строке
> x неизвестно, кроме того, количество типов подстрок тоже неизвестно. То есть нужно определить количество самих подстрок, типов подстрок и дать им значения, чтобы в сумме они давали строку.
А как тогда множество подстрок задается-то? Тот же вопрос про и тд.
И если строка может быть разбита несколькими способами, вас интересует первый попавшийся или по какому-то критерию лучший?
Re: Поиск нескольких подстрок в строке
>А как тогда множество подстрок задается-то? Тот же вопрос про и тд.
Я же написал - подстроки не заданы, их надо найти. Задана строка, а такде списки A, B, C. в которых заданы допустимые значения для a_i, b_i, c_i. соответственно. Количество типов подстрок конечно, но не обязательно в строке каждый тип будет присутствовать.
К примеру, строка http://www.linux.org.ru:8080 содержит 3 подстроки - протокол://, имя сайта, :порт. При этом как протокол, так и порт может отсутствовать, и алгоритм это должен учитывать, например, просто www.linux.org.ru должен выдать один список.
>И если строка может быть разбита несколькими способами, вас интересует первый попавшийся или по какому-то критерию лучший?
Список всех возможных способов.
Фактически нужен наибыстрейший алгоритм разбиения строки на несколько подстрок, количество которых неизвестно, с проверкой данных. Комбинаторная задача, но вдруг есть красивое решение ;)
Re: Поиск нескольких подстрок в строке
> Я же написал - подстроки не заданы, их надо найти. Задана строка, а такде списки A, B, C. в которых заданы допустимые значения для a_i, b_i, c_i. соответственно. Количество типов подстрок конечно, но не обязательно в строке каждый тип будет присутствовать.
Описанное вами задает регулярный язык. В чем проблемы?
> К примеру, строка http://www.linux.org.ru:8080 содержит 3 подстроки - протокол://, имя сайта, :порт. При этом как протокол, так и порт может отсутствовать, и алгоритм это должен учитывать, например, просто www.linux.org.ru должен выдать один список.
список чего?? список вида (protocol='', user='', passwd='',. host='www.linux.org,ru', path='', port='') ?
насколько я знаю, схема URL задается регулярными выражениями. То есть можно написать regexp со скобками
(фигня-всякая-регексповая) фигня-всякая-регексповая ( фигня-всякая-регексповая) и т д
потом запустить regexp matcher и он в скобки поймает подстроки. Скобки могут быть в области действия regexp'овых знаков ? * +, то есть можно отдельные части сделать необязательными.
Посмотрите какой-нибудь tutorial, там это есть. Мне правда непонятно чем вас regexps не устраивают.
А вот с поиском всех вариантов разбиения сложнее. по-моему regexp выдаст match где каждая последующая скобка имеет match максимальной длины. Получить все способы разбиения - это в явном виде не поддерживается и вообще задача нетривиальная, хотя и решаемая.
Re: Поиск нескольких подстрок в строке
>насколько я знаю, схема URL задается регулярными выражениями. То есть можно написать regexp со скобками (фигня-всякая-регексповая) фигня-всякая-регексповая ( фигня-всякая-регексповая) и т д потом запустить regexp matcher и он в скобки поймает подстроки.
Сложно работать с текстом программы, если список допустимых значений - тысячи элементов. Да и потом, поиск по простому списку для регеспов неоптимальный, в отличие от, к примеру, поиска по дереву. Пусть, например, port содержит 10000 значений, что тогда? С регеспом придётся перебирать все значения, что есть комбинаторная задача. При большом количестве строк будет очень низкая производительность.
Re: Поиск нескольких подстрок в строке
> Сложно работать с текстом программы, если список допустимых значений - тысячи элементов.
Не понял. Конструируйте regexp-строку на лету.
> Да и потом, поиск по простому списку для регеспов неоптимальный, в отличие от, к примеру, поиска по дереву. Пусть, например, port содержит 10000 значений, что тогда? С регеспом придётся перебирать все значения, что есть комбинаторная задача. При большом количестве строк будет очень низкая производительность.
Это все полная неправда. Регулярные выражения *компилируются* (man regcomp) в оптимизированные Конечные Автоматы. Никаких переборов при выполнении КА не будет. Почитайте про них что-нибдудь, в сети полно материалов.
Ваша идея, что вы напишете для этого языка распознаватель намного более эффективный чем regexp, вызывает крайний скепсис. Может быть, вы сможете что-то выжать за счет знания вида множетв , . Но даже в этом случае я бы сначала написал код с regexp'ами, благо он очень простой. Как минимум, пригодится как эталоная реалиция для прогонки тестов :-)
Re: Поиск нескольких подстрок в строке
Ну если только конечные автоматы. На первый взгляд приходится работать с весьма нехилой строкой. Если размер не имеет значение, то в принципе подходит.