Сопоставление с образцом

[albobin]

Не очень понял. Код в студию

Код на MUMPSе приводить смысла нет.
Реально у меня в рабочем коде  ввиду того, что в языке (MUMPS) есть операторы сравнения с шаблоном, образец трансформируется в шаблон, а затем одной командой проверяется. Но это к слову. Другой код с циклом сравнения написать не проблема. Поясню  свой предыдущий пост на примере, кстати С.Губанов в принципе про такое же и писал но кратко, без нюансов.

abcdefgabcefg -> abc*efg*efg
1.Образец начинается не со '*' - надо проверить с фикс. позиции (с начала строки) наличие подстроки "abc"
 На конце образца не '*' - надо проверить наличие "efg" на конце строки
 Остаётся проверить "defgabc" ->*efg*
2.Ищем первое же вхождение каждой подстроки из образца в проверяемой строке, пока образец или проверяемая строка не закончится.

Если на первом этапе образец закончился а проверяемая строка нет, то общий итог - строка не соответствует образцу. 
Примерно так всё.
 

[Peter Almazov]

Полный текст на C#. Не причесывал для Assert'ов.

Код: [Выделить]

class Program {
  static string s, p;

  //i - тек. позиция в строке, j - тек. позиция в образце
  static bool Test(int i, int j) {
    bool res = false;
    if (s.Length == i && p.Length == j) {//одновременный конец строк
      res = true;
    } else if (s.Length != i && p.Length == j) {//строка не пустая, образец кончился
      res = false;
    } else if (p.Length != j && p[j] == '*') {
      j++;
      while (i != s.Length+1 && !Test(i, j)) {
        i++;
      }
      res = i != s.Length+1;
    } else if (s.Length != i && p.Length != j) {
      res = s[i] == p[j] && Test(i + 1, j + 1);
    }
    return res;
  }

  static void Main(string[] args) {
    s = "str123";
    p = "*s*r1*34";
    bool res = Test(0, 0);
  }
}


[Geniepro]

Зачем в этой задаче откаты?
В общем виде всё сводится к:
1. Сначала проверить совпадение подстрок в фиксированных местах, а это только может быть на концах строки.
2.Затем проверить наличие остальных подстрок образца по первому же совпадения в оставшейся части проверяемой строки.

Refal-style ))

[albobin]

Полный текст на C#.

а на таких данных как?
строка "str1212"  образец "s*12"

[Peter Almazov]

true

[albobin]

Ещё разок.
строка "str1212"    образец  "s*1t*2"

[Peter Almazov]

false

[Peter Almazov]

Вложил exe-шник. Но потребуется .NET 2.0.

[Berserker]

Исправил. Пропустил случай "конец шаблона, не конец строки = откат".

Код: (delphi) [Выделить]

FUNCTION Match (CONST Str, Pattern: STRING): BOOLEAN;
CONST
  WILLCARD  = '*';

TYPE
  TState  =
  (
    STATE_STRICT_COMPARE,       // [L]
    STATE_FIRST_LETTER_SEARCH,  // *[L]
    STATE_MATCH_SUBSTR_TAIL,    // *L[...]*
    STATE_EXIT
  );

VAR
  State:          TState;
  StrLen:         INTEGER;
  PatternLen:     INTEGER;
  StrBasePos:     INTEGER;
  PatternBasePos: INTEGER;
  s:              INTEGER;  // Pos in Pattern
  p:              INTEGER;  // Pos in Str
 
  PROCEDURE SkipWillcards;
  BEGIN
    WHILE (p <= PatternLen) AND (Pattern[p] = WILLCARD) DO BEGIN
      INC(p);
    END; // .WHILE
  END; // .PROCEDURE SkipWillcards
 
  PROCEDURE SkipMatchingSubstr;
  BEGIN
    WHILE
      (p <= PatternLen)         AND
      (s <= StrLen)             AND
      (Pattern[p] <> WILLCARD)  AND
      (Str[s] = Pattern[p])
    DO BEGIN
      INC(p);
      INC(s);
    END; // .WHILE
  END; // .PROCEDURE SkipMatchingSubstr
 
  PROCEDURE Fail;
  BEGIN
    State   :=  STATE_EXIT;
    RESULT  :=  FALSE;
  END; // .PROCEDURE Fail
 
  PROCEDURE Success;
  BEGIN
    State   :=  STATE_EXIT;
    RESULT  :=  TRUE;
  END; // .PROCEDURE Success

BEGIN
  StrLen          :=  LENGTH(Str);
  PatternLen      :=  LENGTH(Pattern);
  StrBasePos      :=  1;
  PatternBasePos  :=  1;
  s               :=  1;
  p               :=  1;
  State           :=  STATE_STRICT_COMPARE;
  RESULT          :=  FALSE;
 
  WHILE State <> STATE_EXIT DO BEGIN
    CASE State OF
      STATE_STRICT_COMPARE:
        BEGIN
          SkipMatchingSubstr;
         
          IF (s > StrLen) AND (p > PatternLen) THEN BEGIN
            Success;
          END // .IF
          ELSE IF (s > StrLen) OR (p > PatternLen) OR (Pattern[p] <> WILLCARD) THEN BEGIN
            Fail;
          END // .ELSEIF
          ELSE BEGIN
            SkipWillcards;
            State :=  STATE_FIRST_LETTER_SEARCH;
          END; // .ELSE
        END; // .CASE STATE_STRICT_COMPARE
       
      STATE_FIRST_LETTER_SEARCH:
        BEGIN
          WHILE (s < StrLen) AND (Str[s] <> Pattern[p]) DO BEGIN
            INC(s);
          END; // .WHILE
         
          IF s > StrLen THEN BEGIN
            Fail;
          END // .IF
          ELSE BEGIN
            StrBasePos      :=  s;
            PatternBasePos  :=  p;
            INC(p);
            INC(s);
            State           :=  STATE_MATCH_SUBSTR_TAIL;
          END; // .ELSE
        END; // .CASE STATE_FIRST_LETTER_SEARCH
       
      STATE_MATCH_SUBSTR_TAIL:
        BEGIN
          SkipMatchingSubstr;
         
          IF (s > StrLen) AND (p > PatternLen) THEN BEGIN
            Success;
          END // .IF
          ELSE IF s > StrLen THEN BEGIN
            Fail;
          END // .ELSEIF
          ELSE IF (p > PatternLen) OR (Pattern[p] <> WILLCARD) THEN BEGIN
            p     :=  PatternBasePos;
            s     :=  StrBasePos + 1;
            State :=  STATE_FIRST_LETTER_SEARCH;
          END // .ELSEIF
          ELSE BEGIN
            SkipWillcards;
            State :=  STATE_FIRST_LETTER_SEARCH;
          END; // .ELSE
        END; // .CASE STATE_MATCH_SUBSTR_TAIL
    END; // .SWITCH State
  END; // .WHILE
 
  (* If "..." matches, "...*" matches too *)
  IF NOT RESULT THEN BEGIN
    SkipWillcards;
    RESULT  :=  (p > PatternLen) AND (s > StrLen);
  END; // .IF
END; // .FUNCTION Match

ShowMessage(IntToStr(ORD(Match('',            ''))));             // 1
ShowMessage(IntToStr(ORD(Match('a',           ''))));             // 0
ShowMessage(IntToStr(ORD(Match('',            'a'))));            // 0
ShowMessage(IntToStr(ORD(Match('',            '*'))));            // 1
ShowMessage(IntToStr(ORD(Match('aaa',         'bbb'))));          // 0
ShowMessage(IntToStr(ORD(Match('12345abc',    '123*abc'))));      // 1
ShowMessage(IntToStr(ORD(Match('12345abc*d*', '123*abc'))));      // 0
ShowMessage(IntToStr(ORD(Match('abceabcdef',  'abcd*f*'))));      // 0
ShowMessage(IntToStr(ORD(Match('abceabcdef',  '*abcd*f*'))));     // 1
ShowMessage(IntToStr(ORD(Match('abceabcdef',  '*ab*d*f*'))));     // 1
ShowMessage(IntToStr(ORD(Match('abcdefgabcefg',  'abc*efg'))));   // 1
ShowMessage(IntToStr(ORD(Match('abceabcdef',  'abc*efg*efg'))));  // 0

Код: [Выделить]

strict_compare:
  end(Str) & end(Pattern)   =>  success
  end(Str) or end(Pattern)  =>  fail
  mismatch                  =>  fail
  match until willcard      =>  first_letter_search
 
first_letter_search:
  not found =>  fail
  found     =>  match_substr_tail
 
match_substr_tail:
  end(Str) & end(Pattern)   =>  success
  end(Str)                  =>  fail
  end(Pattern) or mismatch  =>  first_letter_search [fallback]
  else                      =>  first_letter_search [continue]

exit:
  only willcards left to match  => success
Особенности: не использует динамическую память, не использует рекурсию.
Откат происходит в следующем месте:

Код: [Выделить]

STATE_MATCH_SUBSTR_TAIL:
  BEGIN
    SkipMatchingSubstr;
   
    ...

    // Шаблон закончился или строка не совпала с той, которую искали
    ELSE IF (p > PatternLen) OR (Pattern[p] <> WILLCARD) THEN BEGIN
      // Откат позиций к запомненным
      p     :=  PatternBasePos;
      s     :=  StrBasePos + 1;
      State :=  STATE_FIRST_LETTER_SEARCH;
    END // .ELSEIF
    ELSE BEGIN
      SkipWillcards;
      State :=  STATE_FIRST_LETTER_SEARCH;
    END; // .ELSE
  END; // .CASE STATE_MATCH_SUBSTR_TAIL

[Peter Almazov]

Врёт.

String: 878765
Pattern: 87*8*7*6
Result: TRUE

[vlad]

2.Ищем первое же вхождение каждой подстроки из образца в проверяемой строке, пока образец или проверяемая строка не закончится.

Кажется понял. В моем варианте "поиск подстроки" это и есть "откат". Т.е. ищем подстроку с текущей позиции, откатываемся, инкрементируем позицию, опять ищем.

[vlad]

2.Ищем первое же вхождение каждой подстроки из образца в проверяемой строке, пока образец или проверяемая строка не закончится.

Кажется понял. В моем варианте "поиск подстроки" это и есть "откат". Т.е. ищем подстроку с текущей позиции, откатываемся, инкрементируем позицию, опять ищем.

Но пока еще не осознал куда деть рекурсию, максимальная глубина которой равна колчичеству подстрок (звездочек).

[albobin]

В моем варианте "поиск подстроки" это и есть "откат".

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

[valexey_u]

В моем варианте "поиск подстроки" это и есть "откат".

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

Это ты про perl (где регэкспы встроенные)? ;-)

[Berserker]

Блин, строка не с нуля индексируется:

Код: [Выделить]

WHILE (s < StrLen) AND (Str[s] <> Pattern[p]) DO BEGIN
=>
WHILE (s <= StrLen) AND (Str[s] <> Pattern[p]) DO BEGIN
Теперь пример Петра Алмазова проходит. Рекурсии всё равно нет.