Intro

Jadi saya sudah membuang-buang waktu lagi meneliti algoritma penyortiran suffix, mengevaluasi ide-ide baru dengan tangan dan dalam kode. Tapi saya selalu berjuang untuk mengingat tipe sufiks saya! Bisakah Anda memberi tahu saya tipe sufiks yang mana?

Paling kiri apa?

Banyak algoritma penyortiran sufiks (SAIS, KA, saya sendiri yang tahu) sufiks menjadi tipe yang berbeda untuk mengurutkannya. Ada dua tipe dasar: sufiks tipe- S dan tipe - L . Sufiks tipe-S adalah sufiks yang secara leksikografis lebih sedikit ( S maller) daripada sufiks berikut dan tipe-L jika sufiksnya lebih besar ( L arger). Sebuah kiri-paling S-type ( LMS-jenis ) hanya itu: A S-jenis akhiran yang diawali dengan L-jenis akhiran.

Hal khusus tentang sufiks tipe-LMS ini adalah bahwa begitu kami mengurutkannya, kami dapat mengurutkan semua sufiks lain dalam waktu linier! Bukankah itu luar biasa?

Tantangan

Diberikan string menganggap itu diakhiri oleh karakter khusus yang kurang dari karakter lain dalam string itu (misalnya lebih kecil daripada byte nol). Keluarkan jenis corrosponding char untuk setiap suffix.

Anda dapat dengan bebas memilih char digunakan untuk jenis tapi aku lebih suka L, S and *untuk L-, S- and LMS-typeselama mereka semua dicetak ( 0x20 - 0x7E).

Contoh

Diberikan mmiissiissiippikeluaran string (saat menggunakan L, S and *):

 LL*SLL*SLL*SLLL

Misalnya yang pertama Ladalah karena fakta yang mmiissiissiippi$secara leksikografis lebih besar dari miissiissiippi$(yang $mewakili karakter minimal yang ditambahkan):

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

Beberapa contoh lagi:

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

Tujuan

Saya di sini bukan untuk mengganggu Peter Cordes (kadang-kadang saya akan melakukan ini di stackoverflow); Saya sangat malas jadi ini tentu saja kode-golf ! Jawaban terpendek dalam byte menang.

Sunting: Urutan karakter diberikan oleh nilai byte mereka. Itu berarti membandingkan harus seperti C strcmp.

Sunting2: Seperti yang dinyatakan dalam komentar komentar harus berupa karakter tunggal untuk setiap karakter input. Sementara saya berasumsi bahwa itu akan dipahami sebagai "mengembalikan sebuah string" tampaknya setidaknya 1 jawaban mengembalikan daftar karakter tunggal. Agar tidak membatalkan jawaban yang ada, saya akan memungkinkan Anda mengembalikan daftar karakter tunggal (atau bilangan bulat yang bila dicetak hanya menghasilkan 1 karakter).

Kiat untuk waktu linier:

1. Ini dapat dilakukan dalam 2 iterasi maju paralel atau dalam satu iterasi mundur tunggal.
2. Keadaan masing-masing sufiks hanya bergantung pada 2 karakter pertama dan tipe yang kedua.
3. Memindai input dalam arah terbalik, Anda dapat menentukan L atau S seperti ini: $t=$c<=>$d?:$t(PHP 7), di mana $ckarakter saat ini $dtipe sebelumnya dan $tsebelumnya.
4. Lihat jawaban PHP saya . Besok aku akan menghadiahkan hadiah itu.

Haskell , 64 53 48 42 byte

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

Cobalah online!

Tidak disatukan, dengan Charalih - alih 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)

Jelly ,  25 23 21 20  19 byte

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

Program lengkap yang mencetak daftar karakter, menggunakan:

L: 0
S: 8
*: 9

(Sebagai tautan, ia mengembalikan daftar di mana semua item adalah karakter kecuali yang terakhir, yang merupakan nol.)

Cobalah online! atau lihat paket tes (dengan konversi keLS*).

Bagaimana?

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

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

Penggunaan 0untuk L,1 untuk S, dan 2untuk *. Bungkus string input dalam karakter kutipan; Saya percaya ini diizinkan oleh konvensi.

Cobalah online!

Contoh penggunaan:

mmiissiissiippi
002100210021000

disimpan 5 byte berkat Leaky Nun, 4 byte terima kasih untuk Ovs

JavaScript (ES6), 51 45 byte

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

Disimpan 6 byte berkat @Neil.

Solusi rekursif untuk latihan ini.

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 byte

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>

Jawaban Port of L3viathan.

C (dentang) , 88 byte

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

Cobalah online!

Haskell , 77 75 byte, waktu linier

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"

Cobalah online!

Bagaimana itu bekerja

Ini menggunakan rekursi, menanggalkan satu karakter pada satu waktu dari awal string. (Jenis string Haskell adalah daftar karakter yang terhubung secara tunggal, sehingga setiap langkah ini adalah waktu yang konstan.)

• Untuk string abc di mana a dan b adalah karakter tunggal dan c adalah string apa pun (mungkin kosong),
  • f ( abc ) = SL e , jika f ( bc ) = L e dan a < b ;
  • f ( abc ) = L * e , jika f ( bc ) = S e dan a > b ;
  • f ( abc ) = LL e , jika f ( bc ) = L e dan a ≥ b ;
  • f ( abc ) = SS e , jika f ( bc ) = S e dan a ≤ b .
• Untuk string karakter tunggal a , f ( a ) = L.

Python 2 , 65 55 byte

Versi rekursif, berdasarkan jawaban L3viathan , menggunakan 012sebagai LS*:

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

Cobalah online!

Python 3 , 65 59 byte

Solusi rekursif menggunakan L, Sdan *:

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

Berjalan melalui string dari depan, dan menggantikan semua instance LSdenganL*

Cobalah online!

PHP, 82 byte, waktu linier

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

Berjalan di atas input dari kanan ke kiri dan mengganti setiap karakter dengan tipe.

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

Menghitung jenis yang diberikan karakter saat ini dan sebelumnya (-1 atau 1). Jika sama jenisnya tidak berubah.

PHP , 70 byte

L = 1, S = 0, * = 2

Dukungan Multibyte diperlukan untuk Testcase terakhir dengan §+3 Bytes mb_substrsebagai gantinyasubstr

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

Cobalah online!

PHP , 71 byte

L = 1, S = 0, * = 2

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

Cobalah online!

PHP , 74 byte

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

Cobalah online!