[問題] 給字串找出第一個符合的glob

[danny0838 (道可道非常道)]

如題，假設資料庫有這樣的鍵-值對：

{
  "www.google.com": function A(){},
  "*.example.com.*": function B(){},
  "*.example.*": function C(){},
  "www.*.com.*": function D(){},
  "*.mycompany.*.com.*": function E(){},
  ...
}

語言是用 javascript。

現在希望對於任意給定的字串，
找出第一個符合的鍵執行對應的function。
例如給 "foo.example.com.tw" 要執行 function B

如果鍵是純字串，做起來很簡單，一個 Map 就解決，
但問題是現在的鍵可能是 glob pattern...

我知道可以用暴力法，
意即依序把每個鍵拿去和給定字串比對，
不過資料庫大起來效能會較差，
想知道是否有時間複雜度較低的演算法可用？

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.164.19.182
※ 文章網址: https://www.ptt.cc/bbs/Programming/M.1506091700.A.BA2.html
※ 編輯: danny0838 (1.164.19.182), 09/22/2017 22:51:54
推 s25g5d4: 轉成 regular expression
→ danny0838: 請問使用RegExp如何降低時間複雜度？
推 CoNsTaR: B 和 C 不會打架嗎？
設計上是有按順序，如果 B 符合了就不執行 C。
※ 編輯: danny0838 (1.164.19.182), 09/23/2017 01:03:59
推 CoNsTaR: map 是用樹做的，你現在的問題是
→ CoNsTaR: 你的鍵其實代表了另一組鍵，而且這組鍵
→ CoNsTaR: (以下稱小鍵)
→ CoNsTaR: 散落在樹的不同地方，所以你的鍵和小鍵
→ CoNsTaR: 對樹來講其實是互不相干的
→ CoNsTaR: 如果你能找到一種排序方式，讓一個鍵所
→ CoNsTaR: 代表的所有小鍵大小連續，那你就能用這
→ CoNsTaR: 種排序方式來建立樹，那時間複雜度就不
→ CoNsTaR: 會和map差太多，不過缺點是我覺得某些情
→ CoNsTaR: 況可能會找不到解
→ CoNsTaR: 還有，其實你的問題可以去 prob solve
→ CoNsTaR:  版問
※ danny0838:轉錄至看板 Prob_Solve                                 09/23 08:07
推 xam: 一樓不是已經解答完這個問題了嗎
推 LaPass: 一樓的解法是正解，但依然還是只能一筆一
→ LaPass: 筆規則下去跑。
推 hijkxyzuw: 建一個表，查不到再一一比對，
→ hijkxyzuw: 用 glob 比對到後就記到表裡。