Модераторы: volvo877, Snowy, MetalFan
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Проверка соответствия шаблону, Подскажите алгоритм 
:(
    Опции темы
SuicideRash
Дата 24.5.2008, 14:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 4
Регистрация: 24.5.2008

Репутация: нет
Всего: нет
Нужно написать програму которая обробатывает 2 строки (образец и шаблон) образец состоит из больших латинских букв, шаблон - большие латинские букви плюс "?" и "*" (?-любой символ, *-любоэ количество, возможно и 0!, любых символов), и выводила "YES" если образец подходит под шаблон,  "NO" - не подходит.

Подскажите идею, можна и текст программы если не тяжело smile
PM MAIL   Вверх
volvo877
Дата 24.5.2008, 15:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2073
Регистрация: 15.11.2004

Репутация: 2
Всего: 116
Поиск по форуму уже не надо использовать?

Поиск подстроки в строке по маске
PM MAIL   Вверх
SuicideRash
Дата 24.5.2008, 19:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 4
Регистрация: 24.5.2008

Репутация: нет
Всего: нет
простите я не нашол...  smile  
PM MAIL   Вверх
SuicideRash
Дата 26.5.2008, 02:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 4
Регистрация: 24.5.2008

Репутация: нет
Всего: нет
Предложенная тема volvo877'м довольно старая, предлагаю поднять єтот вопрос снова, так как приведьонные в ней примеры решений мне удалось очень быстро опровергнут такими примерами:
Строка:
ABBCDPCDA
Шаблон:
A*CDA
Ответ:
должно быть да но выдайот нет
Строка:
ABBCDA
Шаблон
A*CDAK
Ответ:
должно быть нет но выдайот да.
(каждая из 3 програм дайот збой на одном из этих примеров).
У ково есть какие идеи?
У меня есть одна, если получица то виложу результат...
PM MAIL   Вверх
mmvds
Дата 26.5.2008, 12:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 230
Регистрация: 22.12.2007

Репутация: нет
Всего: 6
Строка:
ABBCDPCDA
Шаблон:
A*CDA
Почему это должно быть да? Еслибы шаблон был A*CD*A тогда да, а так нет

Добавлено, а, все, вижу, в конце CDA

Это сообщение отредактировал(а) mmvds - 26.5.2008, 12:03
PM MAIL ICQ   Вверх
volvo877
Дата 26.5.2008, 13:56 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2073
Регистрация: 15.11.2004

Репутация: 2
Всего: 116
SuicideRash, погоняй-ка вот это:

Код
{$B-}
function Match(s, wildcard: string): boolean;
begin
  if wildcard = '' then Match := (s = '')
  else
    case wildcard[1] of
      '*' :
        Match := Match(s, copy(wildcard, 2, 255)) or
          ((s <> '') and Match(copy(s, 2, 255), wildcard));
      '?' :
        Match := (s <> '') and
          (Match(copy(s, 2, 255), copy(wildcard, 2, 255)));
      else
        Match := (s[1] = wildcard[1]) and
          (Match(copy(s, 2, 255), copy(wildcard, 2, 255)));
    end;
end;

begin
  writeln(Match('ABBCDA', 'A*CDAK'), '--> FALSE');
  writeln(Match('ABBCDPCDA', 'A*CDA'), '--> TRUE');
end.
(работать именно в режиме {$B-}, иначе будет переполнение стека!!!)
PM MAIL   Вверх
SuicideRash
Дата 26.5.2008, 19:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 4
Регистрация: 24.5.2008

Репутация: нет
Всего: нет
volvo877 а ти сам её тестировал???
если чесно то я шото не совсем понял как оно проверять будет, а потестировать нет времемни сейчас... как появица обезательно напишу smile
З.Ы. надеюсь она рабочая )
PM MAIL   Вверх
Filon
Дата 26.5.2008, 20:52 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 21
Регистрация: 21.5.2008
Где: Челябинск

Репутация: нет
Всего: нет
Цитата(volvo877 @ 26.5.2008,  11:56)
SuicideRash, погоняй-ка вот это
(работать именно в режиме {$B-}, иначе будет переполнение стека!!!)

Алгоритм правильный, но не лучший в реализации. При длинных исходных строках стек переполняется, даже с {$B-}. Завтра, если будет время, напишу алгоритм без рекурсий.
PM MAIL ICQ   Вверх
volvo877
Дата 26.5.2008, 21:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2073
Регистрация: 15.11.2004

Репутация: 2
Всего: 116
В заголовке добавляем const
Код

function Match(const s, wildcard: string): boolean;


Цитата(Filon @  26.5.2008,  20:52 Найти цитируемый пост)
При длинных исходных строках стек переполняется, даже с {$B-}.
140 символов - достаточно длинная строка? Переполнения стека на подобных размерах не замечено (стек установлен в 32К по умолчанию, TP 7)

Прежде, чем придумывать самостоятельно - сначала лучше посмотреть то, что есть готовое, ибо изобретение велосипедов - занятие неблагодарное:
Wildcard matching algorithms

Это сообщение отредактировал(а) volvo877 - 26.5.2008, 21:02
PM MAIL   Вверх
Filon
Дата 27.5.2008, 08:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 21
Регистрация: 21.5.2008
Где: Челябинск

Репутация: нет
Всего: нет
Цитата(volvo877 @ 26.5.2008,  19:01)
140 символов - достаточно длинная строка? Переполнения стека на подобных размерах не замечено (стек установлен в 32К по умолчанию, TP 7)

Боюсь я испоречен олимпиадным программированием smile
Для меня длинная строка - это строка длиной, например, 500 символов  smile
PM MAIL ICQ   Вверх
volvo877
Дата 27.5.2008, 09:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2073
Регистрация: 15.11.2004

Репутация: 2
Всего: 116
Цитата(Filon @  27.5.2008,  08:54 Найти цитируемый пост)
Для меня длинная строка - это строка длиной, например, 500 символов
Тогда, боюсь, в раздел Паскаль тебе лучше не заходить, ибо паскалевский String ограничен всего 255 символами, и если ты этого не знаешь - ...
PM MAIL   Вверх
Filon
Дата 27.5.2008, 15:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 21
Регистрация: 21.5.2008
Где: Челябинск

Репутация: нет
Всего: нет
Цитата(volvo877 @ 27.5.2008,  07:13)
Тогда, боюсь, в раздел Паскаль тебе лучше не заходить, ибо паскалевский String ограничен всего 255 символами, и если ты этого не знаешь - ...

Я прекрасно знаю, что String ограничен 255 символами. Но мое понимание термина "строка" шире, чем просто паскалевский тип String. Строка может быть представлена и массивом char`ов.
Вообще, думаю, что это мало относится в теме. Так что предлагаю свернуть наш спор smile
PM MAIL ICQ   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Delphi"
THandle
Rrader
volvo877

Запрещается!

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

2. Публиковать ссылки на варез

3. Оффтопить

  • Действия модераторов можно обсудить здесь
  • С просьбами о написании курсовой, реферата и т.п. обращаться сюда
  • Вопросы по реализации алгоритмов рассматриваются здесь
  • 90% ответов на свои вопросы можно найти в DRKB (Delphi Russian Knowledge Base) - крупнейшем в рунете сборнике материалов по Дельфи

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, THandle, Rrader, volvo877.
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Object Pascal: кроссплатформенные технологии | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0481 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.