前綴函數計算

因此，對於下面的子字符串前綴函數計算

1 2 3 4 5 6 7 8 9 10 11 

a b c d a b c d a b x

這是前綴的功能？我和我的一個朋友來計算它，我們有不同的結果，我的是：

a b c d a b c d a b x 

0 0 0 0 1 2 3 4 5 6 2

他：

a b c d a b c d a b x 

0 0 0 0 1 2 3 4 1 2 0

如果我錯了，這是爲什麼？

來源

2015-05-23 user3848412

你可以添加一個簡短的大綱你正在尋找什麼。我們並不是所有人都有這本書在... – DrKoch

僞代碼爲m←長度[P] 一個[1]←0 ķ←0 當q←2至m做而K> 0且p [K + 1]，P [Q]做 ķ←A [k]的端而如果p [K + 1] = p [q]然後 ķ←K + 1 端如果一個[q]←ķ 端爲返回ü – user3848412

@ user3848412請把你的僞代碼到你的問題，這有助於其他閱讀並按照你的問題:) –

前綴表應該是：

a b c d a b c d a b x 
0 0 0 0 1 2 3 4 5 6 0

所以給出兩個版本不正確。

對於你的表的最後一個條目

a b c d a b c d a b x 
0 0 0 0 1 2 3 4 5 6 2 
        ^
        | 
       this one

是正確的a b c d a b c d a b x長度爲2的後綴是b x也必須是它的長度爲2的前綴，這是a b代替。

在前綴表中對應的前綴和後綴從零不同的條目的情況下，已被標記如下表：

你的答案

a      0 
a b      0 
a b c     0 
a b c d     0 

a b c d a    1 
- 
     = 
a b c d a b    2 
--- 
     === 

a b c d a b c   3 
----- 
     ===== 

a b c d a b c d   4 
------- 
     ======= 

a b c d a b c d a  5 
--------- 
     ========= 

a b c d a b c d a b  6 
----------- 
     =========== 

a b c d a b c d a b x 0

來源

2015-05-23 09:18:11 mikyra

感謝您的詳細解釋！ – user3848412

我KMP功能的java：

public int[] KMP(String val) { 
    int i = 0; 
    int j = -1; 
    int[] result = new int[val.length() + 1]; 
    result[0] = -1; 
    while (i < val.length()) { 
     while (j >= 0 && val.charAt(j) != val.charAt(i)) { 
      j = result[j]; 
     } 
     j++; 
     i++; 
     result[i] = j; 
    } 
    return result; 

}

結果爲前綴數組：

[-1, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 0]

來源

2015-05-23 09:02:58

非常感謝！ – user3848412

無論你的答案是正確的。前綴功能或部分匹配表將如下所示：

a b c d a b c d a b x 

0 0 0 0 1 2 3 4 5 6 0

你的答案是高達10指數正確的，但在過去的指數，你做錯了什麼。部分匹配表的索引11的值爲0的原因是因爲沒有合適的前綴匹配索引至索引11的任何正確的後綴。因爲在該位置的所有正確的後綴將以x結尾並且在該位置沒有適當的前綴將以x結束。

如果您在理解實際前綴函數或部分索引表意味着什麼，那麼您可以看看這個document。它有一個非常好的解釋。希望能幫助到你。

來源

2015-05-23 09:16:20 taufique

謝謝你的答案和鏈接，非常感謝！ – user3848412

@ user3848412如果它對你有所幫助，或許upvote不會對你造成任何傷害，對嗎？：P – taufique

兩者都是錯誤的。正確的一個將是

a b c d a b c d a b x 

0 0 0 0 1 2 3 4 5 6 0

來源

2015-05-23 14:07:53

前綴函數計算

回答

相關問題