※ [本文转录自 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

"*" 是否包含 "." ? 若不包含, 那就用 "." 拆分成多个字段吧.