Сравнить слово по маске.

Тема в разделе "Другие языки", создана пользователем Sorcus, 31 дек 2016.

Модераторы: Цукер
  1. Sorcus

    Sorcus Sorcus. A New Beginning.

    Moderator
    Регистр.:
    10 июл 2011
    Сообщения:
    280
    Симпатии:
    575
    Язык не важен, нужен алгоритм. Использование библиотек регулярных выражений избыточен для этой задачи. Нужно решение без использования этих библиотек. Так же решение должно находить совпадение за как можно меньшее количество шагов и быть максимально простым, на сколько это возможно технически.

    Входные данные следующие:
    Домены - example.com, blog.example.com, news.example.com, example.net, example.org
    Маски - *.example.com, news.example.com, shop.example.net, *.org, *net*, news.*

    Результат нужен следующий:
    Домен example.com должен детектиться по маске *.example.com
    Домен blog.example.com должен детектиться по маске *.example.com
    Домен news.example.com должен детектиться по маске *.example.com (*, **)
    Домен example.net должен детектиться по маске *net*
    Домен example.org детектится по маске *.org

    * - Детектится должо по первому совпадению с маской. Т.е. если есть совпадение - прекращаем дальнейшее сравнивание.
    ** - Тем не менее маски news.example.com и news.* так же валидны для домена news.example.com

    Заранее спасибо за помощь :glob:
     
    Последнее редактирование: 31 дек 2016
  2. Duke_Cheb

    Duke_Cheb Создатель

    Регистр.:
    23 янв 2014
    Сообщения:
    22
    Симпатии:
    5
    Маска типа example.*ws не рассматривается? (То есть, с произвольным блоком внутри запроса).
     
  3. Duke_Cheb

    Duke_Cheb Создатель

    Регистр.:
    23 янв 2014
    Сообщения:
    22
    Симпатии:
    5
    Хм... Без подключения библиотек, алгоритм пугающий получается. Семантический разбор строки - вообще штука очень рутинная.

    В общем, на брутальном голом Паскале, будет как-то так...

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

    Наверняка есть небольшая путаница с позицией бегунка i в основном блоке, потом подредактирую. Более быстрого способа разбора не вижу - иные конструкции, которые приходят мне в голову, ведут к уменьшению исходника, но существенному увеличению числа прогонов.

    Протестил не все варианты запросов. Имеются сомнительные.

    В частности, запрос типа "net*" лупит сообщение, что нет совпадений, т.к. случаи с наличием * в обработке отделены от точного поиска. Если ввести просто "net", то сработает корректно и выдаст его позиции в строке.

    Кроме того, отваливается случай маргинального заполнения входных данных. Если во входящей строке inp_potok будет присутствовать адрес, начинающийся с точки, поиск "*.domen" найдет его дважды, как ".domen" и как "domen". Но такой вариант в постановке задачи, как я понимаю, не рассматривается.

    Думаю, можно оптимизировать поиск процентов на двадцать (я не юзал процедуры, да и переменных многовато), но, честно говоря, не оч. хочется. Быстрее от этого он работать не станет, а голову ломать за два часа до нового года неохота. Сам по себе алгоритм жутко сырой, но идея, полагаю, понятна будет.
     

    Вложения:

    • poisk.rar
      Размер файла:
      1,7 КБ
      Просмотров:
      1
    Последнее редактирование: 1 янв 2017
    Sorcus нравится это.
  4. Sorcus

    Sorcus Sorcus. A New Beginning.

    Moderator
    Регистр.:
    10 июл 2011
    Сообщения:
    280
    Симпатии:
    575
    В zip/tar пожалуйста. А то свинское отношение какое-то, выкладывать в .rar :conf:
     
  5. Duke_Cheb

    Duke_Cheb Создатель

    Регистр.:
    23 янв 2014
    Сообщения:
    22
    Симпатии:
    5
    Я пользуюсь ТОЛЬКО rar'ом, причем, наверное, на протяжении последних лет пятнадцати, как и все мои знакомые. Ничего свинского в этом не вижу. Но переархивировать не проблема, конечно.
     

    Вложения:

    • poisk.zip
      Размер файла:
      1,8 КБ
      Просмотров:
      3
    Sorcus нравится это.
  6. Sorcus

    Sorcus Sorcus. A New Beginning.

    Moderator
    Регистр.:
    10 июл 2011
    Сообщения:
    280
    Симпатии:
    575
    Свинство в использовании недокументированных форматов. Каким .rar и является. Проприетарщина как никак...
     
  7. latteo

    latteo Эффективное использование PHP, MySQL

    Moderator
    Регистр.:
    28 фев 2008
    Сообщения:
    1.433
    Симпатии:
    1.219
    Для распаковки есть UnRAR с открытым исходным кодом и под все ОС...
    http://www.rarlab.com/rar_add.htm

    Есть открытый 7-Zip, который умеет открывать RAR.
     
    Duke_Cheb нравится это.
  8. Oxana77

    Oxana77 Создатель Нарушитель

    Регистр.:
    18 окт 2016
    Сообщения:
    21
    Симпатии:
    6
    Если вы экономите вычислительный ресурс вашего кристалла, то язык наверное очень важен!
    т.к не известно что может кушать ваша платформа.
    Если действительно так важен ресурсы, то я бы делала на ассемлере, с базывыми прерываниями.
    Без прерываний ос, и самостоятельно искала в памяти, это самый быстрый способ.
    т.е написала бы функцию поиска по вхождению, делила мнимую строку в памяти на кусочки по вхождению,
    тут же искала совпадения из маски, строка т.е кусок памяти остался целый.
    маску наверное то же побила на кусочки.
    Как-то так!
     
    Sorcus нравится это.
  9. Duke_Cheb

    Duke_Cheb Создатель

    Регистр.:
    23 янв 2014
    Сообщения:
    22
    Симпатии:
    5
    Требовался алгоритм. То есть, программу определенно не собираются лепить на ассемблере - структура на нем будет сильно отличаться от любого ЯП высокого уровня.

    Если же так важна скорость работы, рискну предположить, что вообще планируется использование медленных ИС, типа php или java.
     
    Последнее редактирование: 1 янв 2017