V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
qwertyegg
V2EX  ›  问与答

KMP 里面的部分匹配表构造哪位能解释一下第二层的循环吗?

  •  
  •   qwertyegg · 2020-05-10 01:47:34 +08:00 · 1069 次点击
    这是一个创建于 1419 天前的主题,其中的信息可能已经有所发展或是发生改变。
    fun partialMatchTable(pattern: String): IntArray{
        var pmt = IntArray(pattern.length)
        var j = 0
        for(i in 1 until pattern.length){
        	//下面这个循环怎么理解?
            while(j > 0 && pattern[j] != pattern[i])
                j = pmt[j - 1]        
            pmt[i] = if(pattern[j] == pattern[i]) ++j else j
        }
        return pmt
    }
    

    在 SO( https://stackoverflow.com/questions/38757553) 上有一个解释:

    "if b[i] = j, then for any k < j, s.t P[0..k-1] == P[i-k..i-1], we know that b[j] >= k. At the same time, obviously b[i] > b[j] or b[i] = 0.

    What this means is that we can easily enumerate the k values from largest to smallest, by going through b[i] -> b[b[i]] -> b[b[b[i]]]... and so on. "

    说实话没有太看懂. 部分匹配表 /next 表 /SO 上面的 b,都是一个东西

    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   999 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 20:01 · PVG 04:01 · LAX 13:01 · JFK 16:01
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.