function for suffix array python

Question

I want to write a function that outputs a suffix array. This is what I have so far:

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

This outputs an error because I think I'm missing an additional if statement but I'm not really sure how to go about it. And yes, I know that there are probably easier ways to obtain a suffix array but I'm a beginner in python and there are few functions that I can use. Any help is appreciated. Thanks

Also here's an example of what I want my input and output to be: input --> suffixArray('banana') output--> [5, 3, 1, 0, 4, 2]

Your question isn't entirely clear. Apparently you're looking to output the indices of a suffix array, but not the actual suffix array? That would look like `['a', 'ana', 'anana', 'banana', 'na', 'nana']. — Grismar
– Grismar, Commented Feb 12, 2019 at 3:27

sam46 · Accepted Answer · 2019-02-12 03:29:49Z

5

Apparently you want the index of each suffix after lexicographicly sorting them

s = 'banana'

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

or another way:

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

answered Feb 12, 2019 at 3:29

sam46

1,2819 silver badges12 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Grismar · Accepted Answer · 2019-02-12 03:33:52Z

1

For a simple suffix array:

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

For an array of suffix indices:

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])]

answered Feb 12, 2019 at 3:33

Grismar

32.4k6 gold badges43 silver badges69 bronze badges

Comments

Nikolas Stevenson-Molnar · Accepted Answer · 2019-02-12 03:34:34Z

1

First, generate an array with suffix pairs: the suffix string, and its number:

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

Next, sort this list by the suffix string:

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

Now you can return just the numbers:

return [s[1] for s in suffixes]

Putting it together:

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]

answered Feb 12, 2019 at 3:34

Nikolas Stevenson-Molnar

4,7452 gold badges25 silver badges31 bronze badges

Comments

user9946307 · Accepted Answer · 2021-05-01 19:03:31Z

0

def get_suffix_array(str_sample):
    lis = list(str_sample)
    suffix_array = {v:k for k,v in enumerate(["".join(trim_elem) for trim_elem in [lis[-len(str_sample)+idx:] for idx in range(len(str_sample))]])}
    return [suffix_array.get(k) for k in sorted(list(suffix_array.keys()))]

print(get_suffix_array('banana'))

Result: [5, 3, 1, 0, 4, 2]

answered May 1, 2021 at 19:03

user9946307

Collectives™ on Stack Overflow

function for suffix array python

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related