Introducción

Así que he estado perdiendo mi tiempo nuevamente investigando algoritmos de clasificación de sufijos, evaluando nuevas ideas a mano y en código. ¡Pero siempre me cuesta recordar el tipo de mis sufijos! ¿Me puede decir de qué tipo son mis sufijos?

¿Qué más a la izquierda?

Una gran cantidad de algoritmos de clasificación de sufijos (SAIS, KA, mi propio software daware) agrupan los sufijos en diferentes tipos para ordenarlos. Hay dos tipos básicos: de tipo S y tipo L sufijos. Los sufijos tipo S son sufijos que son lexicográficamente menos ( S menor) que el siguiente sufijo y tipo L si es lexicográficamente mayor ( L arger). Un tipo S más a la izquierda ( tipo LMS ) es solo eso: un sufijo de tipo S precedido por un sufijo de tipo L.

¡Lo especial de estos sufijos de tipo LMS es que una vez que los ordenamos, podemos ordenar todos los demás sufijos en tiempo lineal! ¿No es asombroso?

El reto

Dada una cadena, suponga que está terminada por un carácter especial que es menor que cualquier otro carácter en esa cadena (por ejemplo, más pequeño que incluso el byte nulo). Salida de un tipo de corrosponding char para cada sufijo.

Se puede elegir libremente qué char a utilizar para el tipo, pero yo preferiría L, S and *para L-, S- and LMS-typesiempre y cuando todos ellos son imprimibles ( 0x20 - 0x7E).

Ejemplo

Dado el mmiissiissiippiresultado de la cadena (cuando se usa L, S and *):

 LL*SLL*SLL*SLLL

Por ejemplo, el primero Lse debe al hecho de que mmiissiissiippi$es lexicográficamente mayor que miissiissiippi$( $representa el carácter mínimo agregado):

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

Algunos ejemplos más:

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

Objetivo

No estoy aquí para molestar a Peter Cordes (voy a hacer esto en stackoverflow en algún momento); Soy muy vago, así que, por supuesto, ¡esto es código golf ! La respuesta más corta en bytes gana.

Editar: el orden de los caracteres viene dado por su valor de byte. Eso significa que se comparan deben ser como C de strcmp.

Edit2: como se indica en la salida de comentarios, debe haber un solo carácter para cada carácter de entrada. Si bien supuse que se entendería como "devolver una cadena", parece que al menos 1 respuesta devuelve una lista de caracteres individuales. Para no invalidar las respuestas existentes, le permitiré devolver una lista de caracteres individuales (o enteros que, cuando se imprimen, dan como resultado solo 1 carácter).

Consejos para tiempo lineal:

1. Se puede hacer en 2 iteraciones paralelas hacia adelante o en una única iteración hacia atrás.
2. El estado de cada sufijo depende solo de los primeros 2 caracteres y del tipo del segundo.
3. Al escanear la entrada en dirección inversa, puede determinar L o S de esta manera: $t=$c<=>$d?:$t(PHP 7), donde $cestá el carácter actual $ddel tipo anterior y $tanterior.
4. Ver mi respuesta PHP . Mañana otorgaré la recompensa.

Haskell , 64 53 48 42 bytes

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

Pruébalo en línea!

Sin golf, con en Charlugar 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)

Jalea ,  25 23 21 20  19 bytes

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

Un programa completo que imprime la lista de caracteres, usando:

L: 0
S: 8
*: 9

(Como enlace, devuelve una lista donde todos los elementos son caracteres excepto el último, que es un cero).

Pruébalo en línea! o vea el conjunto de pruebas (con conversión aLS*).

¿Cómo?

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

Usos 0para L, 1para Sy 2para *. Envuelva la cadena de entrada entre comillas; Creo que esto está permitido por convención.

Pruébalo en línea!

Ejemplo de uso:

mmiissiissiippi
002100210021000

ahorrado 5 bytes gracias a Leaky Nun, 4 bytes gracias 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 gracias a @Neil.

Una solución recursiva para el ejercicio.

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>

Puerto de la respuesta de @ 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));}

Pruébalo en línea!

Haskell , 77 75 bytes, tiempo lineal

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"

Pruébalo en línea!

Cómo funciona

Esto utiliza la recursión, quitando un carácter a la vez desde el comienzo de la cadena. (El tipo de cadena de Haskell es una lista de caracteres enlazados individualmente, por lo que cada uno de estos pasos es de tiempo constante).

• Para una cadena abc donde a y b son caracteres individuales yc es cualquier cadena (posiblemente vacía),
  • f ( abc ) = SL e , si f ( bc ) = L e y a < b ;
  • f ( abc ) = L * e , si f ( bc ) = S e y a > b ;
  • f ( abc ) = LL e , si f ( bc ) = L e y a ≥ b ;
  • f ( abc ) = SS e , si f ( bc ) = S e y a ≤ b .
• Para una cadena de un solo carácter a , f ( a ) = L.

Python 2 , 65 55 bytes

Versión recursiva, basada en la respuesta de L3viathan , usando 012como LS*:

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

Pruébalo en línea!

Python 3 , 65 59 bytes

Solución recursiva usando L, Sy *:

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

Se ejecuta a través de la cadena desde el frente y reemplaza todas las instancias de LSconL*

Pruébalo en línea!

PHP, 82 bytes, tiempo lineal

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

Camina sobre la entrada de derecha a izquierda y reemplaza cada carácter con el tipo.

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

Calcula el tipo dado el carácter actual y el carácter anterior (-1 o 1). Si es igual, el tipo no cambia.

PHP , 70 bytes

L = 1, S = 0, * = 2

Se necesita soporte multibyte para el último caso de prueba con los §bytes +3 en su mb_substrlugarsubstr

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

Pruébalo en línea!

PHP , 71 bytes

L = 1, S = 0, * = 2

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

Pruébalo en línea!

PHP , 74 bytes

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

Pruébalo en línea!