Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Поиск по маске

Автор: Fixin 15.12.2004, 19:19

Наверняка вопрос уже был, но я ничего не нашел. Помогите ссылками, или расскажите чем можете помоч smile

Автор: Akina 15.12.2004, 19:36

А чего надо-то? и поподробнее, да?

Автор: 3,14 16.12.2004, 13:13

обработка регулярных выражений не подойдёт?

Автор: Fixin 16.12.2004, 19:34

Цитата

А чего надо-то? и поподробнее, да?

Дано: *ени*; "найти слово по маске в данном выражении"
Ответ: выражЕНИи

Мне нужно узнать толко как определить подходит ли данное слово маске.

Цитата

обработка регулярных выражений не подойдёт?

Это как?

Автор: Петрович 16.12.2004, 21:28

Посмотри http://regexpstudio.com/RU/. Думаю это то что тебе нужно. Даже больше.

Автор: Fixin 18.12.2004, 20:56

Еще есть что-нибудь?

Автор: maxim1000 18.12.2004, 23:20

ну, если интересует сам алгоритм, можно предложить некоторую вариацию на тему динамического программирования:
вводим функцию f(x,y):
1 - если первые x символов тестируемого слова соответствуют y первым y символам маски
0 - иначе
пусть n - длина слова, m - длина маски
тогда задача сводится к определению f(n,m)
а посчитать эту функцию можно рекурсивно:
f(x,y)="или" следующих выражений:
1. слово[x]==маска[y] и f(x-1,y-1)
2. маска[y]=='?' и f(x-1,y-1)
3. маска[y]=='*' и ( f(x-1,y-1) или f(x-1,y) )
для такого вычисления можно сделать матрицу n*m, в ячейках которой будут значения функции
если заняться оптимизацией, можно сохранять только последний столбец и тот, который вычисляется в данный момент

Автор: maxim1000 18.12.2004, 23:45

вот, набросал тут на C++, проверил на нескольких простых примерах, вроде работает...

Код


bool func(char *Word,char *Mask)
{
  int MaskLength;
  bool *OldColumn;
  bool *CurrentColumn;
  bool result;
  int y;
  
  if((Mask[0]!='?')&&(Mask[0]!='*')&&(Mask[0]!=Word[0]))
    return false;
  MaskLength=0;
  while(Mask[MaskLength])
    MaskLength++;
  CurrentColumn=new bool[MaskLength];
  OldColumn=new bool[MaskLength];
  CurrentColumn[0]=true;
  for(y=1;y<MaskLength;y++)
    CurrentColumn[y]=false;
  Word++;
  while(*Word)
  {
    delete[] OldColumn;
    OldColumn=CurrentColumn;
    CurrentColumn=new bool[MaskLength];
    CurrentColumn[0]=(Mask[0]=='*');
    for(y=1;y<MaskLength;y++)
    {
      CurrentColumn[y]=false;
      if(Mask[y]=='*')
        CurrentColumn[y]=OldColumn[y] || OldColumn[y-1] || CurrentColumn[y-1];
      if(Mask[y]==*Word)
        CurrentColumn[y]=OldColumn[y-1];
      if(Mask[y]=='?')
        CurrentColumn[y]=OldColumn[y-1];
    }
    Word++;
  }
  result=CurrentColumn[MaskLength-1];
  delete[] CurrentColumn;
  return result;
}

Автор: Fixin 19.12.2004, 16:18

Сенькваю.

Автор: neutrino 19.12.2004, 21:30

Тема обсуждалась тут: http://forum.vingrad.ru/index.php?act=ST&f=13&t=11581&st=0