Intro

J'ai donc perdu mon temps à rechercher des algorithmes de tri de suffixes, à évaluer de nouvelles idées à la main et dans le code. Mais j'ai toujours du mal à me souvenir du type de mes suffixes! Pouvez-vous me dire de quel type sont mes suffixes?

À gauche quoi?

De nombreux algorithmes de tri des suffixes (SAIS, KA, mon propre daware) regroupent les suffixes en différents types afin de les trier. Il existe deux types de base: type S et de type L suffixes. Les suffixes de type S sont des suffixes qui sont lexicographiquement moins ( S maller) que le suffixe suivant et le type L s'il est lexicographiquement plus grand ( L arger). Un type S le plus à gauche ( type LMS ) n'est que cela: un suffixe de type S précédé d'un suffixe de type L.

La particularité de ces suffixes de type LMS est qu'une fois que nous les avons triés, nous pouvons trier tous les autres suffixes en temps linéaire! N'est-ce pas génial?

Le défi

Étant donné une chaîne, supposons qu'elle se termine par un caractère spécial qui est inférieur à tout autre caractère de cette chaîne (par exemple, plus petit que même l'octet nul). Sortez un caractère corrospondant pour chaque suffixe.

Vous pouvez librement choisir ombles à utiliser pour quel type , mais je préfère L, S and *pour L-, S- and LMS-typeaussi longtemps qu'ils sont imprimables ( 0x20 - 0x7E).

Exemple

Étant donné la mmiissiissiippisortie de la chaîne (lors de l'utilisation L, S and *):

 LL*SLL*SLL*SLLL

Par exemple, le premier Lest dû au fait qu'il mmiissiissiippi$est lexicographiquement supérieur à miissiissiippi$(le $représente le caractère minimal ajouté):

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

Quelques exemples supplémentaires:

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

Objectif

Je ne suis pas ici pour ennuyer Peter Cordes (je vais faire ça sur stackoverflow un jour); Je suis juste très paresseux donc c'est bien sûr du code-golf ! La réponse la plus courte en octets l'emporte.

Edit: l'ordre des caractères est donné par leur valeur d'octet. Cela signifie comparer devrait être comme C de strcmp.

Edit2: Comme indiqué dans les commentaires, la sortie doit être un seul caractère pour chaque caractère d'entrée. Bien que je suppose que cela serait compris comme "renvoyer une chaîne", il semble qu'au moins 1 réponse renvoie une liste de caractères uniques. Afin de ne pas invalider les réponses existantes, je vous permettrai de renvoyer une liste de caractères uniques (ou entiers qui, une fois imprimés, ne donneront que 1 caractère).

Conseils pour le temps linéaire:

1. Cela peut être fait en 2 itérations en avant parallèles ou en une seule itération en arrière.
2. L'état de chaque suffixe ne dépend que des 2 premiers caractères et du type du second.
3. En balayant l'entrée dans le sens inverse, vous pouvez déterminer L ou S comme ceci: $t=$c<=>$d?:$t(PHP 7), où $cest le caractère actuel $ddu type précédent et $tprécédent.
4. Voir ma réponse PHP . Demain, je décernerai la prime.

Haskell , 64 53 48 42 octets

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

Essayez-le en ligne!

Non golfé, avec Charau lieu 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ée ,  25 23 21 20  19 octets

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

Un programme complet qui imprime la liste des caractères, en utilisant:

L: 0
S: 8
*: 9

(En tant que lien, il retourne une liste où tous les éléments sont des caractères sauf le dernier, qui est un zéro.)

Essayez-le en ligne! ou voir la suite de tests (avec conversion en LS*).

Comment?

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

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

Utilise 0pour L, 1pour Set 2pour* . Enveloppez la chaîne d'entrée en guillemets; Je pense que cela est autorisé par la convention.

Essayez-le en ligne!

Exemple d'utilisation:

mmiissiissiippi
002100210021000

économisé 5 octets grâce à Leaky Nun, 4 octets grâce à ovs

JavaScript (ES6), 51 45 octets

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

6 octets enregistrés grâce à @Neil.

Une solution récursive à l'exercice.

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 octets

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 de la réponse de @ L3viathan.

C (clang) , 88 octets

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

Essayez-le en ligne!

Haskell , 77 75 octets, temps linéaire

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"

Essayez-le en ligne!

Comment ça fonctionne

Cela utilise la récursivité, supprimant un caractère à la fois depuis le début de la chaîne. (Le type de chaîne Haskell est une liste de caractères à liaison unique, donc chacune de ces étapes est à temps constant.)

• Pour une chaîne abc où a et b sont des caractères simples et c est une chaîne (éventuellement vide),
  • f ( abc ) = SL e , si f ( bc ) = L e et a < b ;
  • f ( abc ) = L * e , si f ( bc ) = S e et a > b ;
  • f ( abc ) = LL e , si f ( bc ) = L e et a ≥ b ;
  • f ( abc ) = SS e , si f ( bc ) = S e et a ≤ b .
• Pour une chaîne à un seul caractère a , f ( a ) = L.

Python 2 , 65 55 octets

Version récursive, basée sur la réponse de L3viathan , utilisant 012comme LS*:

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

Essayez-le en ligne!

Python 3 , 65 59 octets

Solution récursive à l' aide L, Set *:

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

Exécute la chaîne depuis l'avant et remplace toutes les instances de LSavecL*

Essayez-le en ligne!

PHP, 82 octets, temps linéaire

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

Parcourt l'entrée de droite à gauche et remplace chaque caractère par le type.

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

Calcule le type en fonction du caractère actuel et du caractère précédent (-1 ou 1). Si égal, le type ne change pas.

PHP , 70 octets

L = 1, S = 0, * = 2

La prise en charge multi-octets est nécessaire pour le dernier cas de test avec les §+3 octets à la mb_substrplacesubstr

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

Essayez-le en ligne!

PHP , 71 octets

L = 1, S = 0, * = 2

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

Essayez-le en ligne!

PHP , 74 octets

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

Essayez-le en ligne!