Introdução

Então, eu perdi meu tempo novamente pesquisando algoritmos de classificação de sufixos, avaliando novas idéias manualmente e em código. Mas sempre luto para lembrar o tipo dos meus sufixos! Você pode me dizer qual é o tipo dos meus sufixos?

Mais à esquerda o que?

Muitos algoritmos de classificação de sufixos (SAIS, KA, meu próprio daware) agrupam sufixos em tipos diferentes para classificá-los. Existem dois tipos básicos: S-tipo e tipo L sufixos. Os sufixos do tipo S são sufixos lexicograficamente menores ( S maller) do que o sufixo a seguir e o tipo L, se for lexicograficamente maior ( L arger). O tipo S mais à esquerda ( tipo LMS ) é exatamente isso: Um sufixo do tipo S precedido por um sufixo do tipo L.

O que há de especial nesses sufixos do tipo LMS é que, quando os classificamos, podemos classificar todos os outros sufixos em tempo linear! Isso não é incrível?

O desafio

Dada uma string, suponha que ela seja finalizada por um caractere especial menor que qualquer outro caractere da string (por exemplo, menor que o byte nulo). Saída de um tipo de caractere corrosivo para cada sufixo.

Você pode escolher livremente qual char para usar para que tipo, mas eu prefiro L, S and *para L-, S- and LMS-typecontanto que eles são todos de impressão ( 0x20 - 0x7E).

Exemplo

Dada a mmiissiissiippisaída da string (ao usar L, S and *):

 LL*SLL*SLL*SLLL

Por exemplo, o primeiro Lse deve ao fato de mmiissiissiippi$ser lexicograficamente maior que miissiissiippi$(o $representa o caractere mínimo adicionado):

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$               > $

Mais alguns exemplos:

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

Objetivo

Não estou aqui para irritar Peter Cordes (vou fazer isso no stackoverflow algum dia); Eu sou apenas muito preguiçoso, então isso é claro, código-golfe ! A resposta mais curta em bytes vence.

Edit: A ordem dos caracteres é dada pelo valor em bytes. Isso significa que comparar deve ser como C's strcmp.

Edit2: Como indicado na saída de comentários, deve haver um único caractere para cada caractere de entrada. Embora eu tenha assumido que isso seria entendido como "retornar uma string", parece que pelo menos 1 resposta retorna uma lista de caracteres únicos. Para não invalidar as respostas existentes, permitirei que você retorne uma lista de caracteres únicos (ou números inteiros que, quando impressos, resultam em apenas 1 caractere).

Dicas para o tempo linear:

1. Isso pode ser feito em 2 iterações para frente paralelas ou em uma única iteração para trás.
2. O estado de cada sufixo depende apenas dos 2 primeiros caracteres e do tipo do segundo.
3. Digitalizando a entrada na direção inversa, é possível determinar L ou S assim: $t=$c<=>$d?:$t(PHP 7), onde $cé o caractere atual, $do tipo anterior e $to anterior.
4. Veja minha resposta em PHP . Amanhã vou premiar a recompensa.

Haskell , 64 53 48 42 bytes

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

Experimente online!

Ungolfed, com em Charvez de 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)

Geléia ,  25 23 21 20  19 bytes

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

Um programa completo que imprime a lista de caracteres, usando:

L: 0
S: 8
*: 9

(Como um link, ele retorna uma lista em que todos os itens são caracteres, exceto o último, que é zero.)

Experimente online! ou veja a suíte de testes (com conversão paraLS*).

Como?

Ṛ;\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"

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

Usa 0para L, 1para Se 2para *. Quebra a seqüência de entrada em caracteres de aspas; Eu acredito que isso é permitido por convenção.

Experimente online!

Exemplo de uso:

mmiissiissiippi
002100210021000

economizou 5 bytes graças a Leaky Nun, 4 bytes graças a ovs

JavaScript (ES6), 51 45 bytes

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

Guardado 6 bytes graças a @Neil.

Uma solução recursiva para o exercício.

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

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>

Porto da resposta do @ L3viathan.

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));}

Experimente online!

Haskell , 77 75 bytes, tempo linear

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"

Experimente online!

Como funciona

Isso usa recursão, removendo um caractere de cada vez desde o início da string. (O tipo de sequência Haskell é uma lista de caracteres vinculados individualmente, portanto, cada uma dessas etapas é de tempo constante.)

• Para uma sequência abc em que a e b são caracteres únicos ec é qualquer sequência (possivelmente vazia),
  • f ( abc ) = SL e , se f ( BC ) = G e e um < b ;
  • f ( abc ) = L * e , se f ( bc ) = S e e a > b ;
  • f ( abc ) = LL e , se f ( bc ) = L e e a ≥ b ;
  • f ( abc ) = SS e , se f ( bc ) = S e e a ≤ b .
• Para uma sequência de caracteres únicos a , f ( a ) = L.

Python 2 , 65 55 bytes

Versão recursiva, baseada na resposta de L3viathan , usando 012como LS*:

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

Experimente online!

Python 3 , 65 59 bytes

Solução recursiva utilizando L, Se *:

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

Executa a string pela frente e substitui todas as instâncias de LSporL*

Experimente online!

PHP, 82 bytes, tempo linear

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

Percorre a entrada da direita para a esquerda e substitui cada caractere pelo tipo.

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

Calcula o tipo dado o atual e o caractere anterior (-1 ou 1). Se igual, o tipo não muda.

PHP , 70 bytes

L = 1, S = 0, * = 2

Suporte de vários bytes é necessária para a última Testcase com as §+3 Bytes mb_substrvezsubstr

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

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

Experimente online!

PHP , 74 bytes

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

Experimente online!