Alfred/Sublime Text 里的 Substring Matching 是如何实现的？

2015-04-13 07:25:55 +08:00
 Valyrian
Alfred输入框和Sublime Text的Command Palette 输入进东西后给的suggestion都是substring matching。比如一个命令是abc，那么可以用ab，bc，ac匹配到，但不能用ba，ca。简而言之，就是一个subsequence matching。（参考： http://en.wikipedia.org/wiki/Longest_common_subsequence_problem ）

用什么数据结构可以实现这样高效的搜索？
2147 次点击
所在节点    问与答
6 条回复
jokester
2015-04-13 08:47:49 +08:00
suffix array?
jokester
2015-04-13 08:57:59 +08:00
nop NVM
ffffwh
2015-04-13 09:19:43 +08:00
这不是经典的动态规划例子么
ffffwh
2015-04-13 09:21:31 +08:00
@ffffwh
不不，看错
phoenixlzx
2015-04-13 10:13:05 +08:00
之前姬家有人问过
我当时想的是正则贪婪匹配一个array
（自己没试过
phoenixlzx
2015-04-13 10:52:21 +08:00
我错了，没学过算法的本渣渣还是匿了吧
下面有菊苣们的回答
https://plus.google.com/+PhoenixNemo/posts/iHHuQWeN1yE

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/183326

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX