# What type are my suffixes?

## 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 ! 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. • This is my first question :) Sandbox got two upvotes and no comments so I think its ready to be posted. Feel free to make suggestions ! – Christoph Jun 13 '17 at 5:55 • What characters can appear in the input? – Martin Ender Jun 13 '17 at 5:58 • @MartinEnder all chars your string supports e.g. even the null byte for c++ style strings. Think of it as binary data. – Christoph Jun 13 '17 at 5:59 • What does * mean? – Leaky Nun Jun 13 '17 at 6:03 • @LeakyNun * means the corresponding suffix is of type left most s-type. A S-type suffix that is preceeded by a L-type suffix.. – Christoph Jun 13 '17 at 6:05 ## 10 Answers # Haskell, 645348 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)  • Anonymous functions are allowed, so the z= can be removed. – Ørjan Johansen Jun 13 '17 at 15:17 • I just can't read Haskell. Would you mind giving me a brief explaination? – Christoph Jun 13 '17 at 17:04 • @Christoph : the go function takes two arguments. The first is the character that represents what should be used to describe the S situation. The second is a string. It goes through that string recursively, removing the first character at each step (that's what tail does). The trick is that the first argument is set to * when the previous result was a L, or S otherwise. That way, in the case where an * or an S should be used, that first argument can be used directly. Hope that makes sense. – bartavelle Jun 13 '17 at 20:58 • That's quite a nice idea ! I'm hoping to see more clever ideas :) – Christoph Jun 13 '17 at 21:04 • @ØrjanJohansen how am I supposed to prepare the result in TIO? – bartavelle Jun 13 '17 at 21:36 # 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"  • Would you mind adding a small explaination for me ? – Christoph Jun 13 '17 at 7:37 • I will do of course - I am thinking about possible golfs first... – Jonathan Allan Jun 13 '17 at 7:37 • 17 bytes – Leaky Nun Jun 13 '17 at 9:42 • @LeakyNun How did you work that out?! You are using a bug there I think + on strings seems to vectorise but the underlying results are not actually Jelly iterables but strings (!) (e.g. try +@/L€ or +@/L€€ or ...) – Jonathan Allan Jun 13 '17 at 10:48 • @JonathanAllan yes, + produces actual string. This is an undocumented feature, or what you call bug. – Leaky Nun Jun 13 '17 at 10:51 # Python 3, 92877469 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 # 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 • Save 6 bytes: f=(c,d)=>c&&(d<(d=c<(c=c.slice(1))))+d+f(c,d) – Neil Jun 13 '17 at 18:38 • Thanks, @Neil, I knew there had to be an optimization in there somewhere. – Rick Hitchcock Jun 13 '17 at 18:53 ## 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. • @RickHitchcock Oops, somehow I managed to port c=1 as c=0... – Neil Jun 13 '17 at 18:35 # 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! # 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 ab;
• f(abc) = SSe, if f(bc) = Se and ab.
• For a single-character string a, f(a) = L.
• Could you please provide an explanation? – R. Kap Jun 19 '17 at 20:32
• Please provide a description so I can validate that this runs in linear time. – Christoph Jun 22 '17 at 5:51
• @Christoph Added. – Anders Kaseorg Jun 22 '17 at 6:54
• @AndersKaseorg thanks for adding ! Sadly this seems quite verbose compared to the other Haskell answer. Could this be golfed further by not using S, L and *? – Christoph Jun 22 '17 at 7:16
• @Christoph To be clear, [1,1,2,0,1,1,2,0,1,1,2,0,1,1,1] is a list of single-digit numbers, not a list of single chars. In my case, I think outputting a list of numbers would not save me any bytes. – Anders Kaseorg Jun 22 '17 at 9:19

# 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 andc+(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!

• blah if s else''s and blah saves six bytes. In Python 2, str(blah)blah saves another three bytes on the second solution. – Anders Kaseorg Jun 22 '17 at 9:58

## 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.

• +1 for the idea with strtr – Jörg Hülsermann Jun 24 '17 at 12:58

# 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!

• $s=&$argn quite clever ! I'm pretty sure there is a better answer though ;) Hopefully someone comes up with it :) – Christoph Jun 13 '17 at 16:56
• @Christoph I have the feeling that I am miss something. I have try to store the last LS* in a varibale but it is longer – Jörg Hülsermann Jun 13 '17 at 17:01
• @Christoph mean you like so? I coul not really seen why the last testcase is false Try it online! – Jörg Hülsermann Jun 13 '17 at 20:08
• @Christoph Okay I have seen it why it not works for the last testcase I must use mb_substr instead of substr if the input is not in the simple ascii range. Is it necessary to support the last testcase? – Jörg Hülsermann Jun 13 '17 at 20:51
• @Christoph Thank You In this case I ignore the last testcase with the § – Jörg Hülsermann Jun 13 '17 at 21:05