python - 在构造后缀数组之前在 Python 中指定字符串结尾标记

Question

我正在 http://portal.acm.org/citation.cfm?id=1813708 中实现算法利用后缀数组来查找最长的公共(public)子串。这些算法涉及为字符串构造一个后缀数组，该数组是一组给定字符串与称为哨兵的字符串分隔符的串联。例如，如果给定字符串 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 是提供的字符串数量)的最有效机制是什么？

Answer 1

您可以使用 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'