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) OR (p > PatternLen) THEN BEGIN
Fail;
END // .ELSEIF
ELSE IF Pattern[p] <> WILLCARD THEN BEGIN
p := PatternBasePos + 1;
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
Таблица переходов:
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) or end(Pattern) => fail
match until willcard => first_letter_search
mismatch => match_substr_tail
exit:
only willcards left to match => success
Не судите строго.
