我在http://portal.acm.org/citation.cfm?id=1813708中实现了利用后缀数组查找最长公共子串的算法。该算法涉及为字符串构造一个后缀数组，该数组是一组给定字符串与称为哨兵的字符串分隔符的串联。例如，如果给定字符串 a、b 和 c，则会创建一个新字符串 d，它是 a$1b$2c$3，其中 $1、$2、$3 是标记每个字符串结尾的标记字符。标记字符必须是唯一的，并且在字典顺序上少于 a、b 和 c 中的所有其他字符。
我的问题围绕 Python 中哨兵字符的表示展开。如果 a、b 和 c 是 ASCII 字符串，我想我可能需要将这些字符串转换为 UTF-8 并将它们的范围从 0-127 转移到更高的范围，以便有可用的字符在字典上少于那些在字符串。如果这看起来合理，那么在 Python 中重新映射字符以使其范围为 N-127+N 的最有效机制是什么，其中 N 是提供的字符串数？
您可以使用 Unicode（不是 UTF-8）字符串来执行此操作。在 Python 3 中，所有字符串都是 Unicode，但在 Python 2 中，您需要u前缀（即"hello"不是 Unicode，而是u"world"是）。
>>> s = u"string one"
>>> N = 3
>>> "".join(unichr(ord(x) + N) for x in s)
u'vwulqj#rqh'
对于 Python 3，这会稍微简单一些：
>>> s = "string one"
>>> N = 3
>>> "".join(chr(ord(x) + N) for x in s)
'vwulqj#rqh'
我认为您应该使用标记器并将每个字符串替换为整数。那么对于哨兵来说，就会剩下很多整数。可能，使用较大的整数作为哨兵比使用小的整数更方便。对于打印输出，您可以使用任何所需的 Unicode 字符，也可以对所有字符使用相同的字符。
您正在实施 Yamamoto & Church 吗？如果是这样，请在开始之前查看一些较新的文献。我推荐 Abouelhoda et al Extended Suffix Array 和 Kim, Kim & Park, Linearized Suffix Trees。如果您喜欢组合数学，请查看：Schürmann、Klaus-Bernd、Suffix 数组的理论和实践。
另外，我推荐 3 路基数快速排序，而不是专门的后缀排序算法。如果您的语料库中有冗余，您只需要后缀排序算法。但是这些冗余是不必要的，并且会搞砸你的统计数据。
如果你做了一些有趣的事情，我很想看看
戴尔·格德曼