Wprowadzenie

Więc marnuję swój czas, ponownie badając algorytmy sortowania sufiksów, oceniając nowe pomysły ręcznie i w kodzie. Ale zawsze staram się zapamiętać rodzaj moich sufiksów! Czy możesz mi powiedzieć, jakiego typu są moje sufiksy?

Najbardziej lewe co?

Wiele algorytmów sortowania sufiksów (SAIS, KA, mój własny daware) grupuje sufiksy do różnych typów w celu ich posortowania. Istnieją dwa podstawowe typy: typu S i L typu przyrostki. Sufiksy typu S to sufiksy, które są leksykograficznie mniejsze ( S maller) niż następujący sufiks i typ L, jeśli jest leksykograficznie większy ( L arger). Najbardziej lewy typ S ( typ LMS ) to po prostu: sufiks typu S poprzedzony sufiksem typu L.

Cechą szczególną tych sufiksów typu LMS jest to, że po ich posortowaniu możemy posortować wszystkie pozostałe sufiksy w czasie liniowym! Czy to nie jest niesamowite?

Wyzwanie

Podany ciąg znaków zakłada, że ​​jest zakończony znakiem specjalnym, który jest mniejszy niż jakikolwiek inny znak w tym ciągu (np. Mniejszy niż nawet bajt zerowy). Wypisuje znak typu corrosponding dla każdego przyrostka.

Można dowolnie wybrać, które char do użytku, do którego typu, ale wolałbym L, S and *na L-, S- and LMS-typetak długo, jak są one wszystkie do druku ( 0x20 - 0x7E).

Przykład

Biorąc pod uwagę ciąg mmiissiissiippiwyjściowy (przy użyciu L, S and *):

 LL*SLL*SLL*SLLL

Na przykład pierwszy Lwynika z faktu, że mmiissiissiippi$jest leksykograficznie większy niż miissiissiippi$( $reprezentuje dodany minimalny znak):

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

Kilka innych przykładów:

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

Cel

Nie jestem tu po to, by drażnić Petera Cordesa (kiedyś zrobię to przy przepełnieniu stosu); Jestem po prostu bardzo leniwy, więc to jest oczywiście golf golfowy ! Najkrótsza odpowiedź w bajtach wygrywa.

Edycja: Kolejność znaków jest podana według wartości bajtów. Oznacza to porównanie powinno być jak C użytkownika strcmp.

Edycja2: Jak podano w komentarzach, wyjście powinno być pojedynczym znakiem dla każdego znaku wejściowego. Chociaż założyłem, że byłoby to rozumiane jako „zwróć ciąg”, wydaje się, że co najmniej 1 odpowiedź zwraca listę pojedynczych znaków. Aby nie unieważniać istniejących odpowiedzi, pozwolę ci zwrócić listę pojedynczych znaków (lub liczb całkowitych, które po wydrukowaniu dają tylko 1 znak).

Wskazówki dotyczące czasu liniowego:

1. Można to zrobić w 2 równoległych iteracjach do przodu lub w jednej iteracji do tyłu.
2. Stan każdego sufiksu zależy tylko od pierwszych 2 znaków i rodzaju drugiego.
3. Skanując dane wejściowe w odwrotnym kierunku, możesz określić L lub S w następujący sposób: $t=$c<=>$d?:$t(PHP 7), gdzie $cjest obecny znak $dpoprzedniego i $tpoprzedniego typu.
4. Zobacz moją odpowiedź na PHP . Jutro przyznam nagrodę.

Haskell , 64 53 48 42 bajtów

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

Wypróbuj online!

Bez golfa, z Charzamiast 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)

Galaretka ,  25 23 21 20  19 bajtów

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

Pełny program, który drukuje listę znaków, używając:

L: 0
S: 8
*: 9

(Jako link zwraca listę, w której wszystkie elementy są znakami, z wyjątkiem ostatniego, który wynosi zero.)

Wypróbuj online! lub zobacz pakiet testowy (z konwersją naLS*).

W jaki sposób?

Ṛ;\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 bajtów

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

Używa 0do L, 1do Si 2do *. Zawiń łańcuch wejściowy w znaki cudzysłowu; Wierzę, że jest to dozwolone przez konwencję.

Wypróbuj online!

Przykładowe zastosowanie:

mmiissiissiippi
002100210021000

zapisano 5 bajtów dzięki Leaky Nun, 4 bajty dzięki ovs

JavaScript (ES6), 51 45 bajtów

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

Zaoszczędź 6 bajtów dzięki @Neil.

Rekurencyjne rozwiązanie ćwiczenia.

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 bajty

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 odpowiedzi @ L3viathan.

C (clang) , 88 bajtów

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

Wypróbuj online!

Haskell , 77 75 bajtów, czas liniowy

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"

Wypróbuj online!

Jak to działa

Wykorzystuje rekurencję, usuwając jeden znak na raz od początku łańcucha. (Typ łańcucha Haskell jest pojedynczo połączoną listą znaków, więc każdy z tych kroków ma charakter stały).

• Dla łańcuchów abc gdzie i b są pojedyncze znaki, a C jest dowolny (ewentualnie puste) ciąg
  • f ( abc ) = SL e , jeśli f ( bc ) = L e i a < b ;
  • f ( abc ) = L * e , jeśli f ( bc ) = S e i a > b ;
  • f ( abc ) = LL e , jeśli f ( bc ) = L e i a ≥ b ;
  • f ( abc ) = SS e , jeżeli f ( bc ) = S e i a ≤ b .
• W przypadku ciągu jednego znaku a , f ( a ) = L.

Python 2 , 65 55 bajtów

Wersja rekurencyjna, oparta na odpowiedzi L3viathan , wykorzystująca 012jako LS*:

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

Wypróbuj online!

Python 3 , 65 59 bajtów

Roztwór rekurencyjne użyciu L, Si *:

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

Prowadzi ciąg od przodu i zastępuje wszystkie wystąpienia LS zL*

Wypróbuj online!

PHP, 82 bajty, czas liniowy

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

Przechodzi nad wejściem od prawej do lewej i zamienia każdy znak na typ.

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

Oblicza typ na podstawie bieżącego i poprzedniego znaku (-1 lub 1). Jeśli równy, typ się nie zmienia.

PHP , 70 bajtów

L = 1, S = 0, * = 2

Obsługa wielobajtowa jest potrzebna w ostatnim Testcase z §+3 Bytes mb_substrzamiastsubstr

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

Wypróbuj online!

PHP , 71 bajtów

L = 1, S = 0, * = 2

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

Wypróbuj online!

PHP , 74 bajty

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

Wypróbuj online!