修改通用後綴樹以保持節點出現在文本字符串中的次數

Question

如何修改Ukkonen's paper中的過程以保存單詞在文本中出現的次數值。有沒有提供字符串頻率的這樣的實現？

我想要的修改就像是一個字符串「嘿嘿」所有「h」，「e」，「他」在樹中應該是2的頻率計數。其餘節點的默認值爲1.

我發現了一些圖書館，如the best so far和以前的一些問題，如this。

但他們都沒有描述一個足夠好的解決方案來解決我的問題。另外我必須處理一個非常大的字典文件（大約十億字）。那麼算法需要非常快。而且我已經準備好在太空中妥協一下了。

Answer 1

答案可以在這裏找到：Counting the number of substrings

基本上，構建後綴樹，匹配從根開始的子字符串並將計數低於該點的葉節點。這是該詞出現在文本中的次數。