Поиск нескольких подстрок в строке

А что мешает собрать регулярное выражение

(a1 | a2 | ... | ax) (b1| b2| ...|bx) ... (z1|... zx)

и искать его?

x неизвестно, кроме того, количество типов подстрок тоже неизвестно. То есть нужно определить количество самих подстрок, типов подстрок и дать им значения, чтобы в сумме они давали строку.

> x неизвестно, кроме того, количество типов подстрок тоже неизвестно. То есть нужно определить количество самих подстрок, типов подстрок и дать им значения, чтобы в сумме они давали строку.

А как тогда множество подстрок {a1, a2 ... ax} задается-то? Тот же вопрос про {b1, b2 ... } и тд.

И если строка может быть разбита несколькими способами, вас интересует первый попавшийся или по какому-то критерию лучший?

>А как тогда множество подстрок {a1, a2 ... ax} задается-то? Тот же вопрос про {b1, b2 ... } и тд.

Я же написал - подстроки не заданы, их надо найти. Задана строка, а такде списки A, B, C..., в которых заданы допустимые значения для a_i, b_i, c_i... соответственно. Количество типов подстрок конечно, но не обязательно в строке каждый тип будет присутствовать.

К примеру, строка http://www.linux.org.ru:8080 содержит 3 подстроки - протокол://, имя сайта, :порт. При этом как протокол, так и порт может отсутствовать, и алгоритм это должен учитывать, например, просто www.linux.org.ru должен выдать один список.

>И если строка может быть разбита несколькими способами, вас интересует первый попавшийся или по какому-то критерию лучший?

Список всех возможных способов.

Фактически нужен наибыстрейший алгоритм разбиения строки на несколько подстрок, количество которых неизвестно, с проверкой данных. Комбинаторная задача, но вдруг есть красивое решение ;)

> Я же написал - подстроки не заданы, их надо найти. Задана строка, а такде списки 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 максимальной длины. Получить все способы разбиения - это в явном виде не поддерживается и вообще задача нетривиальная, хотя и решаемая.

>насколько я знаю, схема URL задается регулярными выражениями. То есть можно написать regexp со скобками (фигня-всякая-регексповая) фигня-всякая-регексповая ( фигня-всякая-регексповая) и т д потом запустить regexp matcher и он в скобки поймает подстроки.

Сложно работать с текстом программы, если список допустимых значений - тысячи элементов. Да и потом, поиск по простому списку для регеспов неоптимальный, в отличие от, к примеру, поиска по дереву. Пусть, например, port содержит 10000 значений, что тогда? С регеспом придётся перебирать все значения, что есть комбинаторная задача. При большом количестве строк будет очень низкая производительность.

> Сложно работать с текстом программы, если список допустимых значений - тысячи элементов.

Не понял. Конструируйте regexp-строку на лету.

> Да и потом, поиск по простому списку для регеспов неоптимальный, в отличие от, к примеру, поиска по дереву. Пусть, например, port содержит 10000 значений, что тогда? С регеспом придётся перебирать все значения, что есть комбинаторная задача. При большом количестве строк будет очень низкая производительность.

Это все полная неправда. Регулярные выражения *компилируются* (man regcomp) в оптимизированные Конечные Автоматы. Никаких переборов при выполнении КА не будет. Почитайте про них что-нибдудь, в сети полно материалов.

Ваша идея, что вы напишете для этого языка распознаватель намного более эффективный чем regexp, вызывает крайний скепсис. Может быть, вы сможете что-то выжать за счет знания вида множетв {a_i}, {b_i}. Но даже в этом случае я бы сначала написал код с regexp'ами, благо он очень простой. Как минимум, пригодится как эталоная реалиция для прогонки тестов :-)

Ну если только конечные автоматы... На первый взгляд приходится работать с весьма нехилой строкой. Если размер не имеет значение, то в принципе подходит.