Home Sign Up Sign In
Valyrian
V2EX  ›  问与答

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

  •   
  •   Valyrian · Apr 13, 2015 · 3042 views
    This topic created in 4229 days ago, the information mentioned may be changed or developed.
    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 ）

    用什么数据结构可以实现这样高效的搜索？
  • matching
  • substring
  • Text
    6 replies  •  2015-04-13 10:52:21 +08:00
    jokester
    jokester
    Apr 13, 2015
    1
    suffix array?
    jokester
    jokester
    Apr 13, 2015
    2
    nop NVM
    ffffwh
    ffffwh
    Apr 13, 2015
    3
    这不是经典的动态规划例子么
    ffffwh
    ffffwh
    Apr 13, 2015
    4
    @ffffwh
    不不，看错
    phoenixlzx
    phoenixlzx
    Apr 13, 2015 via Android
    5
    之前姬家有人问过
    我当时想的是正则贪婪匹配一个array
    （自己没试过
    phoenixlzx
    phoenixlzx
    Apr 13, 2015 via Android
    6
    我错了，没学过算法的本渣渣还是匿了吧
    下面有菊苣们的回答
    https://plus.google.com/+PhoenixNemo/posts/iHHuQWeN1yE
    About   ·   Help   ·   Advertise   ·   Blog   ·   API   ·   FAQ   ·   Privacy   ·   Solana   ·   4659 Online   Highest 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 01:54 · PVG 09:54 · LAX 17:54 · JFK 20:54
    ♥ Do have faith in what you're doing.