Delphi 通配符模式匹配函數 IsLike：支援 ? * 遞迴回溯演算法實作

前言

Delphi 標準庫缺乏通配符模式匹配函數。本文提供一個獨立的 IsLike(Pattern, Text) 函數，支援 ? (單字元) 與 * (多字元) 通配符，採用遞迴回溯演算法正確處理複雜模式 (如 *a*b*c*、?*?)。

完整函數實作

function IsLike(const Pattern, Text: string): Boolean;
var
  pIdx, tIdx: Integer;
  pLen, tLen: Integer;
  starPos, matchPos: Integer;
begin
  // 統一轉小寫進行不區分大小寫比較
  // 若需區分大小寫，移除 LowerCase
  var Pat := LowerCase(Pattern);
  var Txt := LowerCase(Text);
  
  pLen := Length(Pat);
  tLen := Length(Txt);
  pIdx := 1;
  tIdx := 1;
  starPos := 0;      // 記錄 Pattern 中最後一個 * 的位置
  matchPos := 0;     // 記錄 Text 中對應 * 匹配的起始位置
  
  while tIdx <= tLen do
  begin
    // 情況 1: 字元匹配 或 ? 匹配任意單字元
    if (pIdx <= pLen) and ((Pat[pIdx] = Txt[tIdx]) or (Pat[pIdx] = '?')) then
    begin
      Inc(pIdx);
      Inc(tIdx);
    end
    // 情況 2: 遇到 *，記錄位置並假設匹配 0 字元
    else if (pIdx <= pLen) and (Pat[pIdx] = '*') then
    begin
      starPos := pIdx;
      matchPos := tIdx;
      Inc(pIdx); // * 本身不消耗 Text 字元，移至 Pattern 下一字元
    end
    // 情況 3: 失配但之前有 *，回溯：讓 * 多吞一個字元
    else if starPos > 0 then
    begin
      // 回溯到 * 位置
      pIdx := starPos + 1;
      // * 多匹配一個字元
      Inc(matchPos);
      tIdx := matchPos;
    end
    // 情況 4: 失配且無 * 可回溯，匹配失敗
    else
    begin
      Result := False;
      Exit;
    end;
  end;
  
  // Text 已處理完，檢查 Pattern 剩餘是否全為 *
  while (pIdx <= pLen) and (Pat[pIdx] = '*') do
    Inc(pIdx);
  
  Result := (pIdx > pLen);
end;

測試驗證

procedure TestIsLike;
var
  Tests: array of record
    Pattern, Text: string;
    Expected: Boolean;
  end;
  I: Integer;
begin
  Tests := [
    ('abc', 'abc', True),
    ('abc', 'abcd', False),
    ('a?c', 'abc', True),
    ('a?c', 'ac', False),
    ('a*c', 'abc', True),
    ('a*c', 'ac', True),
    ('a*c', 'axxxc', True),
    ('*abc*', '123abc456', True),
    ('*abc*', 'abc', True),
    ('*a*b*c*', '1a2b3c4', True),
    ('*a*b*c*', 'abc', True),
    ('?*?', 'a', True),
    ('?*?', 'ab', True),
    ('?*?', '', False),
    ('*.txt', 'readme.txt', True),
    ('*.txt', 'readme.doc', False),
    ('file?.log', 'file1.log', True),
    ('file?.log', 'file12.log', False),
    ('', '', True),
    ('*', '', True),
    ('?', '', False)
  ];
  
  for I := 0 to High(Tests) do
  begin
    var Res := IsLike(Tests[I].Pattern, Tests[I].Text);
    if Res <> Tests[I].Expected then
      WriteLn(Format('FAIL: Pattern="%s" Text="%s" Got=%s Exp=%s', 
        [Tests[I].Pattern, Tests[I].Text, BoolToStr(Res), BoolToStr(Tests[I].Expected)]))
    else
      WriteLn(Format('OK: "%s" =~ "%s"', [Tests[I].Pattern, Tests[I].Text]));
  end;
end;

演算法原理解析

採用雙指標 + 回溯點記錄：

1. pIdx 掃描 Pattern，tIdx 掃描 Text
2. 遇到 * 記錄 starPos (Pattern 位置) 與 matchPos (Text 位置)，假設 * 匹配 0 字元，繼續匹配後續
3. 後續失配時，若有 starPos > 0，回溯：* 多吞一個字元 (matchPos++)，重試
4. Text 結束後，Pattern 剩餘必須全為 * 才算成功

效能特性

• 時間複雜度：最壞 O(m×n) (大量 * 回溯)，典型 O(m+n)
• 空間複雜度：O(1) 常數空間，無遞迴堆疊
• 支援極長字串 (受限於 Integer 索引上限 2GB)

擴展：支援字元類別 [abc]、範圍 [a-z]

function IsLikeEx(const Pattern, Text: string): Boolean;
// 在情況 1 擴展：
// if Pat[pIdx] = '[' then
//   解析字元類別，檢查 Txt[tIdx] 是否在集合中
//   支援 [abc]、[a-z]、[^abc] 否定
//   找到對應 ']' 後繼續
// ...
end;

替代方案比較

結語

IsLike 以 30 行核心程式碼實作了工業級通配符匹配，適合檔案名過濾、日誌關鍵字搜尋、簡單規則引擎等場景。若需正則表達式完整功能，請直接使用 TRegEx；但對於單純 ?/* 模式，本函數零依賴、高效能、易整合，是最佳選擇。