Intro

Deshalb habe ich wieder meine Zeit damit verschwendet, nach Suffix-Sortieralgorithmen zu suchen und neue Ideen von Hand und im Code zu bewerten. Aber ich habe immer Mühe, mich an die Art meiner Suffixe zu erinnern! Können Sie mir sagen, welcher Typ meine Suffixe sind?

Ganz links was?

Viele Suffix-Sortieralgorithmen (SAIS, KA, meine eigene Daware) gruppieren Suffixe in verschiedene Typen, um sie zu sortieren. Es gibt zwei Grundtypen: S-Typ- und L-Typ- Suffixe. Suffixe vom Typ S sind Suffixe, die lexikographisch kleiner ( S maller) sind als das folgende Suffix und L-Typ, wenn sie lexikographisch größer sind ( L arger). Ein S-Typ ganz links ( LMS-Typ ) ist genau das: Ein S-Typ- Suffix, dem ein L-Typ- Suffix vorangestellt ist .

Das Besondere an diesen Suffixen vom Typ LMS ist, dass wir nach dem Sortieren alle anderen Suffixe in linearer Zeit sortieren können! Ist das nicht großartig?

Die Herausforderung

Angenommen, eine Zeichenfolge wird durch ein Sonderzeichen abgeschlossen, das kleiner als jedes andere Zeichen in dieser Zeichenfolge ist (z. B. kleiner als das Nullbyte). Geben Sie für jedes Suffix ein entsprechendes Zeichen aus.

Sie können frei wählen , welche Zeichen für welche Art zu verwenden , aber ich würde es vorziehen , L, S and *für L-, S- and LMS-typeso lange , wie sie alle druckbaren sind ( 0x20 - 0x7E).

Beispiel

Angesichts der String- mmiissiissiippiAusgabe (bei Verwendung L, S and *):

 LL*SLL*SLL*SLLL

Zum Beispiel ist das erste Lauf die Tatsache zurückzuführen, dass mmiissiissiippi$es lexikographisch größer ist als miissiissiippi$(das $repräsentiert das hinzugefügte Minimalzeichen):

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

Einige weitere Beispiele:

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

Tor

Ich bin nicht hier, um Peter Cordes zu ärgern (ich werde das irgendwann beim Stackoverflow tun); Ich bin nur sehr faul, das ist natürlich Code-Golf ! Die kürzeste Antwort in Bytes gewinnt.

Bearbeiten: Die Reihenfolge der Zeichen wird durch ihren Bytewert angegeben. Das heißt, vergleichen sollte wie C sein strcmp.

Edit2: Wie in den Kommentaren angegeben, sollte die Ausgabe für jedes Eingabezeichen ein einzelnes Zeichen sein. Obwohl ich davon ausgegangen bin, dass dies als "Rückgabe einer Zeichenfolge" verstanden wird, scheint mindestens 1 Antwort eine Liste einzelner Zeichen zurückzugeben. Um die vorhandenen Antworten nicht ungültig zu machen, können Sie eine Liste einzelner Zeichen (oder Ganzzahlen, die beim Drucken nur 1 Zeichen ergeben) zurückgeben.

Tipps für die lineare Zeit:

1. Dies kann in 2 parallelen Vorwärtsiterationen oder in einer einzelnen Rückwärtsiteration erfolgen.
2. Der Status jedes Suffix hängt nur von den ersten beiden Zeichen und dem Typ des zweiten ab.
3. Durch Scannen des Eingangs in umgekehrter Richtung können Sie L oder S wie folgt bestimmen: $t=$c<=>$d?:$t(PHP 7), wobei $cdas aktuelle Zeichen $dder vorherige und $tder vorherige Typ ist.
4. Siehe meine PHP-Antwort . Morgen werde ich das Kopfgeld vergeben.

Haskell , 64 53 48 42 Bytes

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

Probieren Sie es online aus!

Ungolfed, mit Charanstelle von 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)

Gelee ,  25 23 21 20  19 Bytes

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

Ein vollständiges Programm, das die Liste der Zeichen druckt und dabei Folgendes verwendet:

L: 0
S: 8
*: 9

(Als Link wird eine Liste zurückgegeben, in der alle Elemente Zeichen sind, mit Ausnahme des letzten, bei dem es sich um eine Null handelt.)

Probieren Sie es online aus! oder sehen Sie sich die Testsuite an (mit Konvertierung inLS*).

Wie?

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

Verwendet 0für L, 1für Sund 2für *. Wickeln Sie die Eingabezeichenfolge in Anführungszeichen. Ich glaube, das ist konventionell erlaubt.

Probieren Sie es online aus!

Anwendungsbeispiel:

mmiissiissiippi
002100210021000

5 Bytes dank Leaky Nun gespart, 4 Bytes dank Ovs

JavaScript (ES6), 51 45 Byte

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

6 Bytes dank @Neil gespeichert.

Eine rekursive Lösung für die Übung.

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>

Port von @ L3viathans Antwort.

C (Klirren) , 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));}

Probieren Sie es online aus!

Haskell , 77 75 Bytes, lineare Zeit

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"

Probieren Sie es online aus!

Wie es funktioniert

Hierbei wird eine Rekursion verwendet, bei der jeweils ein Zeichen vom Anfang der Zeichenfolge entfernt wird. (Der Haskell-Zeichenfolgentyp ist eine einfach verknüpfte Liste von Zeichen, daher ist jeder dieser Schritte zeitkonstant.)

• Für eine Zeichenfolge abc, bei der a und b einzelne Zeichen sind und c eine beliebige (möglicherweise leere) Zeichenfolge ist,
  • f ( abc ) = SL e , wenn f ( bc ) = L e und a < b ;
  • f ( abc ) = L * e , wenn f ( bc ) = S e und a > b ;
  • f ( abc ) = LL e , wenn f ( bc ) = L e und a ≥ b ;
  • f ( abc ) = SSe , wenn f ( bc ) = Se und a ≤ b .
• Für eine Einzelzeichenfolge a ist f ( a ) = L.

Python 2 , 65 55 Bytes

Rekursive Version, basierend auf L3viathan Antwort , mit 012wie LS*:

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

Probieren Sie es online aus!

Python 3 , 65 59 Bytes

Rekursive Lösung mit L, Sund *:

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

Läuft von vorne durch die Zeichenfolge und ersetzt alle Instanzen von LSdurchL*

Probieren Sie es online aus!

PHP, 82 Byte, lineare Zeit

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

Überläuft die Eingabe von rechts nach links und ersetzt jedes Zeichen durch den Typ.

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

Berechnet den Typ anhand des aktuellen und des vorherigen Zeichens (-1 oder 1). Wenn gleich, ändert sich der Typ nicht.

PHP , 70 Bytes

L = 1, S = 0, * = 2

Für den letzten Testfall mit den §+3 Bytes wird mb_substrstattdessen Multibyte-Unterstützung benötigtsubstr

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

Probieren Sie es online aus!

PHP , 71 Bytes

L = 1, S = 0, * = 2

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

Probieren Sie es online aus!

PHP , 74 Bytes

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

Probieren Sie es online aus!