※ [本文轉錄自 Programming 看板 #1PnIAqkY ]
作者: danny0838 (道可道非常道) 看板: Programming
標題: [問題] 給字串找出第一個符合的glob
時間: Fri Sep 22 22:48:18 2017
如題，假設資料庫有這樣的鍵-值對：
{
"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...
我知道可以用暴力法，
意即依序把每個鍵拿去和給定字串比對，
不過資料庫大起來效能會較差，
想知道是否有時間複雜度較低的演算法可用？

https://goo.gl/MgPcNR https://goo.gl/6rDNDb 像這樣的?

雖然也可以把很多個 pattern 一起弄成一個 DFA 不過不知道這 DFA 會多大[email protected]@啊, 沒看到一樓貼的 paper

"*" 是否包含 "." ? 若不包含, 那就用 "." 拆分成多個欄位吧.