What type are my suffixes?

Question

Intro

So I've been wasting my time again researching suffix sorting algorithms, evaluating new ideas by hand and in code. But I always struggle to remember the type of my suffixes! Can you tell me which type my suffixes are?

Left-most what?

A lot of suffix sorting algorithms (SAIS, KA, my own daware) group suffixes into different types in order to sort them. There are two basic types: S-type and L-type suffixes. S-type suffixes are suffixes that are lexicographically less (Smaller) than the following suffix and L-type if it is lexicographically greater (Larger). A left-most S-type (LMS-type) is just that: A S-type suffix that is preceeded by a L-type suffix.

The special thing about these LMS-type suffixes is that once we sorted them we can sorted all the other suffixes in linear time ! Isn't that awesome?

The challenge

Given a string assume it is terminated by a special character that is less than any other character in that string (e.g. smaller than even the null byte). Output a type corrosponding char for each suffix.

You can freely choose which char to use for which type but I'd prefer L, S and * for L-, S- and LMS-type as long as they are all printable (0x20 - 0x7E).

Example

Given the string mmiissiissiippi output (when using L, S and *):

 LL*SLL*SLL*SLLL

For example the first L is due to the fact that mmiissiissiippi$ is lexicographically greater than miissiissiippi$ (the $ represents the added minimal character):

L - mmiissiissiippi$ > miissiissiippi$
L - miissiissiippi$  > iissiissiippi$
* - iissiissiippi$   < issiissiippi     and preceeded by L
S - issiissiippi$    < ssiissiippi$
L - ssiissiippi$     > siissiippi$
L - siissiippi$      > iissiippi$
* - iissiippi$       < issiippi$        and preceeded by L
S - issiippi$        < ssiippi$
L - ssiippi$         > siippi$
L - siippi$          > iippi$
* - iippi$           < ippi$            and preceeded by L
S - ippi$            < ppi$
L - ppi$             > pi$
L - pi$              > i$
L - i$               > $

Some more examples:

"hello world" -> "L*SSL*L*LLL"
"Hello World" -> "SSSSL*SSLLL"
"53Ab§%5qS"   -> "L*SSL*SLL"

Goal

I'm not here to annoy Peter Cordes (I'm so gonna do this on stackoverflow sometime); I'm just very lazy so this is of course code-golf ! The shortest answer in bytes wins.

---

Edit: The order of the chars is given by their byte value. That means compare should be like C's strcmp.

Edit2: Like stated in the comments output should be a single character for each input character. While I assumed that would be understood as "return a string" it seems at least 1 answer returns a list of single characters. In order to not invalidate the existing answers I will allow you to return a list of single characters (or integers which when printed result in only 1 char).

---

Tips for linear time:

1. It can be done in 2 parallel forward iterations or in a single backward iteration.
2. The state of each suffix depends only on the first 2 chars and the type of the second.
3. Scanning the input in reverse direction you can determine L or S like this: $t=$c<=>$d?:$t (PHP 7), where $c is the current char $d the previous and $t the previous type.
4. See my PHP answer. Tomorrow I will award the bounty.

Answer 1

Haskell, 64 53 48 42 bytes

(0!)
k!(x:y)|x:y>y=1:2!y|2>1=k:0!y
_![]=[]

Try it online!

Ungolfed, with Char instead of Int:

suffixes :: String -> String
suffixes = go 'S'
 where
   go :: Char -> String -> String
   go _ "" = ""
   go lorstar s | s > tail s = 'L' : go '*' (tail s)
                | otherwise  = lorstar : go 'S' (tail s)

Answer 2

Jelly,  25 23 21 20  19 bytes

Ṛ;\UỤỤIṠµI2n×ịØDṚ;0

A full program that prints the list of characters, using:

L: 0
S: 8
*: 9

(As a link it returns a list where all items are characters except the last one, which is a zero.)

Try it online! or see the test suite (with conversion to LS*).

How?

Ṛ;\UỤỤIṠµI2n×ịØDṚ;0 - Link: list of characters, s  e.g. "cast"
Ṛ                   - reverse                           "tsac"
  \                 - cumulative reduce by:
 ;                  -   concatenation                   ["t","ts","tsa","tsac"]
   U                - upend (reverse each)              ["t","st","ast","cast"] (suffixes)
    Ụ               - sort indexes by value             [3,4,2,1] (lexicographical order)
     Ụ              - sort indexes by value             [4,3,1,2] (order of that)
      I             - incremental differences           [-1,-2,1] (change)
       Ṡ            - sign                              [-1,-1,1] (comparisons)
        µ           - monadic chain separation, call that x
         I          - incremental differences           [0,2] (only (-1,1) produce 2s)
          2         - literal 2                         2
           n        - not equal?                        [1,0] (indexes of * will be 0)
            ×       - multiply by x (vectorises)        [-1,0,1] (make indexes of *s 0)
              ØD    - decimal yield                     "0123456789"
             ị      - index into (1-indexed & modular)  ['8','9','0']
                Ṛ   - reverse                           ['0','9','8']
                 ;0 - concatenate a zero                ['0','9','8',0]
                    - implicit print                     0980
                    -                              i.e. "L*SL"

Answer 3

Python 3, 92 87 74 69 65 bytes

s=input()
c=1
while s:d=s<s[1:];print(d+(c<d),end='');s=s[1:];c=d

Uses 0 for L, 1 for S, and 2 for *. Wrap the input string in quote characters; I believe this is allowed by convention.

Try it online!

Example use:

mmiissiissiippi
002100210021000

saved 5 bytes thanks to Leaky Nun, 4 bytes thanks to ovs

Answer 4

JavaScript (ES6), 51 45 bytes

f=(c,d)=>c&&(d<(d=c<(c=c.slice(1))))+d+f(c,d)

Saved 6 bytes thanks to @Neil.

A recursive solution to the exercise.

f=(c,d)=>c&&(d<(d=c<(c=c.slice(1))))+d+f(c,d)

console.log(f('mmiissiissiippi')); //LL*SLL*SLL*SLLL   002100210021000
console.log(f('hello world'));     //L*SSL*L*LLL       02110202000
console.log(f('Hello World'));     //SSSSL*SSLLL       11110211000
console.log(f('53Ab§%5qS'));       //L*SSL*SLL         021102100

Answer 5

JavaScript (ES6), 52 bytes

f=
s=>s.replace(/./g,_=>(c<(c=s<(s=s.slice(1))))+c,c=1)

<input oninput=o.textContent=f(this.value)><pre id=o>

Port of @L3viathan's answer.

Answer 6

C (clang), 88 bytes

S(S,A,I)char*S,*A;{for(;strlen(S);A=S,S++,printf("%c",I=strcmp(A,S)>0?76:I==76?42:83));}

Try it online!

Answer 7

Haskell, 77 75 bytes, linear time

f(a:b:c)|let g"L"|a<b="SL";g"S"|a>b="L*";g d=d++d;d:e=f$b:c=g[d]++e
f _="L"

Try it online!

How it works

This uses recursion, stripping off one character at a time from the beginning of the string. (The Haskell string type is a singly-linked list of characters, so each of these steps is constant-time.)

• For a string abc where a and b are single characters and c is any (possibly empty) string,
  • f(abc) = SLe, if f(bc) = Le and a < b;
  • f(abc) = L*e, if f(bc) = Se and a > b;
  • f(abc) = LLe, if f(bc) = Le and a ≥ b;
  • f(abc) = SSe, if f(bc) = Se and a ≤ b.
• For a single-character string a, f(a) = L.

Answer 8

Python 2, 65 55 bytes

Recursive version, based on L3viathan's answer, using 012 as LS*:

def g(s,d=2):c=s<s[1:];return s and`c+(d<c)`+g(s[1:],c)

Try it online!

Python 3, 65 59 bytes

Recursive solution using L, S, and *:

f=lambda s:s and('LS'[s<s[1:]]+f(s[1:])).replace('LS','L*')

Runs through the string from the front, and replaces all instances of LSwith L*

Try it online!

Answer 9

PHP, 82 byte, linear time

for($a=$argn;a&$c=$a[$i-=1];$d=$c)$a[$i]=2+$t=$d<=>$c?:$t;echo strtr($a,[13=>12]);

Walks over the input from right to left and replaces each char with the type.

$t=$d<=>$c?:$t

Calculates the type given the current and the previous char (-1 or 1). If equal the type doesn't change.

Answer 10

PHP, 70 bytes

L = 1, S = 0 , * = 2

Multibyte Support is needed for the last Testcase with the § +3 Bytes mb_substr instead substr

for(;$s=&$argn;$s=$u)$r.=$l=($l&1)+(1&$l^($s>$u=substr($s,1)));echo$r;

Try it online!

PHP, 71 bytes

L = 1, S = 0 , * = 2

for(;$s=&$argn;$s=$u)$r.=+($s>$u=substr($s,1));echo strtr($r,[10=>12]);

Try it online!

PHP, 74 bytes

for(;$s=&$argn;$s=$u)$r.=SL[$s>$u=substr($s,1)];echo strtr($r,[LS=>"L*"]);

Try it online!