功能为后缀数组蟒

Question

我想写输出后缀阵列功能。这是我到目前为止有：

def suffixArray(s):
    sa = []
    for i in range(len(s)):
        suffix= sorted([s[i:]])
        sa = [len(s)-len(suffix[i:])
    return list(sa)

因为我觉得我失去了一个额外的if语句，但我真的不知道如何去了解它这个输出错误。是的，我知道有可能是更容易的方式来获得一个后缀数组，但我在python初学者和有，我可以使用一些功能。任何帮助表示赞赏。谢谢

还这里的我想要我的输入和输出是一个例子：输入 - > suffixArray（“香蕉”）输出 - > [5,3，1，0，4，2]

Answer 1

显然，你希望每个后缀的索引之后lexicographicly对它们进行排序

s = 'banana'

>>> [t[1] for t in sorted((s[i:],i) for i in range(len(s)))]
[5, 3, 1, 0, 4, 2]

或者另一种方式：

>>> sorted(range(len(s)), key=lambda i: s[i:])
[5, 3, 1, 0, 4, 2]

Answer 2

对于一个简单的后缀数组：

s = 'banana'
sa = sorted([s[i:] for i in range(len(s))])

对于后缀索引的数组：

s = 'banana'
usd = {i: s[i:] for i in range(len(s))
sai = [x for x, _ in sorted(d.items(), key=lambda x: x[1])]

Answer 3

首先，生成具有后缀对的数组：后缀串，并且其数：

suffixes = [(s[i:], i) for i in range(len(s))]

接下来，排序该列表由字尾字符串：

suffixes.sort(key=lambda x: x[0])

现在，你可以回到刚才的数字：

return [s[1] for s in suffixes]

把它放在一起：

def suffixArray(s):
    suffixes = [(s[i:], i) for i in range(len(s))]
    suffixes.sort(key=lambda x: x[0])

    return [s[1] for s in suffixes]