Home Sign Up Sign In
Valyrian
V2EX  ›  问与答

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

  •   
  •   Valyrian · Apr 13, 2015 · 2692 views
    This topic created in 4054 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
        1
    jokester  
       Apr 13, 2015
    suffix array?
    jokester
        2
    jokester  
       Apr 13, 2015
    nop NVM
    ffffwh
        3
    ffffwh  
       Apr 13, 2015
    这不是经典的动态规划例子么
    ffffwh
        4
    ffffwh  
       Apr 13, 2015
    @ffffwh
    不不，看错
    phoenixlzx
        5
    phoenixlzx  
       Apr 13, 2015 via Android
    之前姬家有人问过
    我当时想的是正则贪婪匹配一个array
    （自己没试过
    phoenixlzx
        6
    phoenixlzx  
       Apr 13, 2015 via Android
    我错了，没学过算法的本渣渣还是匿了吧
    下面有菊苣们的回答
    https://plus.google.com/+PhoenixNemo/posts/iHHuQWeN1yE
    About   ·   Help   ·   Advertise   ·   Blog   ·   API   ·   FAQ   ·   Solana   ·   5407 Online   Highest 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 49ms · UTC 06:40 · PVG 14:40 · LAX 23:40 · JFK 02:40
    ♥ Do have faith in what you're doing.