我不是一個巨大的數學書呆子，所以我可能很容易遺漏一些東西，但是讓我們從https://cp-algorithms.com/string/z-function.html中獲取演算法并嘗試將其應用于 string baz。這個字串肯定有一個子字串集'b'，'a'，'z'，'ba'，'az'，'baz'。
讓我們看看 z 函式是如何作業的（至少我是怎么理解的）：
- 我們取一個空字串并在其中添加“b”。根據演算法 z[0] = 0 的定義，因為它對于大小 1 是未定義的；
- 我們取 'b' 并添加 'a' ，反轉字串，我們有 'ab'... 現在我們計算 z 函式... 它產生 {0, 0}。第一個元素是“未定義”的，第二個元素應該定義為：
i-th element is equal to the greatest number of characters starting from the position i that coincide with the first characters of s.
所以，在 i = 1 處，我們有 'b'，我們的字串以 a 開頭，'b' 與 'a' 不重合，所以當然 z[i=1]=0。這將在整個單詞中重復。最后，我們留下了全零的 z 陣列，盡管字串有 6 個子字串，但它并沒有告訴我們任何資訊。
我錯過了什么嗎？有很多網站推薦 z 功能，count of distinct substrings但它......不起作用？我是不是誤解了distinct這里的意思？
見測驗用例：https ://pastebin.com/mFDrSvtm
uj5u.com熱心網友回復：
當您在字串 S 的開頭添加一個字符x時，S的所有子字串仍然是xS的子字串，但是您得到了多少個新子字串？
- 新的子字串都是xS的前綴。這些有長度（xS），但是
- 其中的max(Z( xS )) 已經是S的子字串，所以
- 你得到 length( xS ) - max(Z( xS )) 新的
因此，給定一個字串 S，只需將 S的每個后綴P的所有長度 ( P ) - max(Z( P )) 相加即可。
您的測驗用例baz有 3 個后綴：z、az和baz. 所有字母都是不同的，因此它們的 Z 函式處處為零。結果是不同子串的數量只是后綴長度的總和：3 2 1 = 6。
嘗試baa：Z 函式中唯一的非零值是 Z('aa')[1] = 1，因此唯一子串的數量為 3 2 - 1 1 = 5。
請注意，您鏈接到的文章提到這是一個 O(n 2 ) 演算法。這是正確的，盡管它的開銷很低。通過構建后綴樹可以在 O(n) 時間內完成此操作，但這非常復雜。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/477977.html