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,都是一个东西
1
QingchuanZhang 2020-05-10 06:12:56 +08:00 1
|