使用manber myers算法的后缀数组
使用manber myers算法的后缀数组
提问于 2013-08-28 18:37:49
我在论文“http://webglimpse.net/pubs/suffix.pdf”中试过了这个理论
但当他们说我有点迷茫
设Ai是Pos1桶中的first suffix (即Pos = i)，并考虑Ai (如果in <0时，则忽略Ai并取fi的suffix等)。由于Ai以最小的h-符号字符串开头，所以在其2h桶中，Ai-h应该是first。
我听不懂这句话。如果i-h < 0，为什么会忽略Ai？当第一阶段i-h >0时，位置是如何确定的？
其中一个样本是http://belbesy.wordpress.com/2012/10/10/spoj-649-distinct-substrings-suffix-arrays-nlgn/
回答 1
Stack Overflow用户
回答已采纳
发布于 2017-04-28 16:57:25
我强烈建议，与其尝试理解C++代码，不如手动遍历这个Manbers后缀数组构造算法的Python实现，以获得一个简单的5个字符示例。
因为Python版本只有15行代码，所以很容易理解。
即使您不理解Python，也要将其视为伪代码，并搜索您不理解的语法。
就我个人而言，我用手走过了一个5字串，这足以帮助我理解算法是如何工作的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/18495728
复制相关文章
相似问题
腾讯云开发者
