5-1-1.png

5-1-2.png

　http://http://pl-learning-blog.logdown.com/posts/1084611

 

5-1-3.png

5-1-4.png

5-1-5.png

 

failure function 的計算方式

for(int i = 1; i<P_len; i++) {
    int tmp = f[i-1];
    while (tmp && P[i] != P[tmp])
        tmp = f[tmp-1];

        if (P[i] == P[tmp])
            f[i] = tmp + 1;
        else
            f[i] = 0;
}

 

一樣: f(i) = f(i-1) + 1

不一樣: ... 很難解釋, 舉個例子

abcabdxxxabcabc

000120xxx123453        <= f(i)

如果 c 是 d 的話, 則可以填入 6 因為從 b 接續下去, 就有 6 個字元一樣了 (abcabd)

但 c 不是 d , 於是我們找 b 的次佳解, 於是從 f[ b ] 找到 b , 且 b 記錄著次佳解 (ab)

因為 f[ b ] == 5 , 所以從 b 往前 5 個字元會跟從 b 往前 5 個字元一樣, 所以從 b 往下接續等同從 b 往下接續

但為什麼 b 會記錄次佳解 ?

因為在 b 沒有 abcab 

我已經盡力解釋了 ...

 

 

5-1-7.png

arrow
arrow
    全站熱搜
    創作者介紹
    創作者 大神（偽） 的頭像
    大神（偽）

    大神的世界

    大神（偽） 發表在 痞客邦 留言(0) 人氣()

    E-mail轉寄