вступление

Поэтому я снова тратил время на исследование алгоритмов сортировки суффиксов, оценку новых идей вручную и в коде. Но я всегда пытаюсь вспомнить тип моих суффиксов! Можете ли вы сказать мне, какой тип моих суффиксов?

Левый самый что?

Многие алгоритмы сортировки суффиксов (SAIS, KA, мое собственное daware) группируют суффиксы в разные типы для их сортировки. Существует два основных типа: суффиксы S-типа и L-типа . Суффиксы S-типа - это суффиксы, которые лексикографически меньше ( S maller), чем следующий суффикс, и L-типа, если они лексикографически больше ( L arger). Крайний левый S-тип ( LMS-тип ) - это просто суффикс S-типа, которому предшествует суффикс L-типа .

Особенность этих суффиксов типа LMS заключается в том, что как только мы их отсортируем, мы можем отсортировать все другие суффиксы за линейное время! Разве это не круто?

Соревнование

Учитывая, что строка предполагает, что она заканчивается специальным символом, который меньше, чем любой другой символ в этой строке (например, меньше, чем даже нулевой байт). Выведите тип соответствующего символа для каждого суффикса.

Вы можете свободно выбирать, какой символ использовать для какого типа, но я бы предпочел, L, S and *чтобы L-, S- and LMS-typeвсе они печатались ( 0x20 - 0x7E).

пример

Учитывая mmiissiissiippiвывод строки (при использовании L, S and *):

 LL*SLL*SLL*SLLL

Например, первое Lсвязано с тем, что mmiissiissiippi$лексикографически больше, чем miissiissiippi$( $символ представляет добавленный минимальный символ):

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

Еще несколько примеров:

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

Цель

Я здесь не для того, чтобы раздражать Питера Кордеса (я так собираюсь когда-нибудь сделать это на stackoverflow); Я просто очень ленив, так что это, конечно, код-гольф ! Самый короткий ответ в байтах побеждает.

Изменить: порядок символов определяется их байтовым значением. Это означает, что сравнение должно быть как у strcmp.

Edit2: как указано в выводе комментариев должен быть один символ для каждого входного символа. Хотя я предполагал, что это будет пониматься как «вернуть строку», кажется, что хотя бы один ответ возвращает список из отдельных символов. Чтобы не сделать недействительными существующие ответы, я позволю вам вернуть список из отдельных символов (или целых чисел, которые при печати приводят только к 1 символу).

Советы по линейному времени:

1. Это может быть сделано в 2 параллельных прямых итерациях или в одной обратной итерации.
2. Состояние каждого суффикса зависит только от первых двух символов и типа второго.
3. Сканируя ввод в обратном направлении, вы можете определить L или S следующим образом: $t=$c<=>$d?:$t(PHP 7), где $cтекущий символ $dпредыдущего и $tпредыдущего типа.
4. Смотрите мой ответ PHP . Завтра я буду награждать награду.

Haskell , 64 53 48 42 байта

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

Попробуйте онлайн!

Ungolfed, с Charвместо 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)

Желе ,  25 23 21 20  19 байт

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

Полная программа, которая печатает список символов, используя:

L: 0
S: 8
*: 9

(В качестве ссылки он возвращает список, в котором все элементы являются символами, кроме последнего, который равен нулю.)

Попробуйте онлайн! или посмотрите набор тестов (с преобразованием вLS*).

Как?

Ṛ;\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 байт

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

Использует 0для L, 1для Sи 2для *. Оберните входную строку в кавычки; Я считаю, что это разрешено соглашением.

Попробуйте онлайн!

Пример использования:

mmiissiissiippi
002100210021000

сэкономили 5 байтов благодаря Leaky Nun, 4 байта благодаря ovs

JavaScript (ES6), 51 45 байт

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

Сохранено 6 байтов благодаря @Neil.

Рекурсивное решение для упражнения.

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 байта

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>

Порт @ L3viathan ответ.

C (лязг) , 88 байт

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

Попробуйте онлайн!

Haskell , 77 75 байтов, линейное время

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"

Попробуйте онлайн!

Как это работает

При этом используется рекурсия, удаляющая по одному символу за раз от начала строки. (Тип строки Haskell представляет собой односвязный список символов, поэтому каждый из этих шагов выполняется в постоянном времени.)

• Для строки abc, где a и b - отдельные символы, а c - любая (возможно, пустая) строка,
  • f ( abc ) = SL e , если f ( bc ) = L e и a < b ;
  • f ( abc ) = L * e , если f ( bc ) = S e и a > b ;
  • f ( abc ) = LL e , если f ( bc ) = L e и a ≥ b ;
  • f ( abc ) = SS e , если f ( bc ) = S e и a ≤ b .
• Для односимвольной строки a , f ( a ) = L.

Python 2 , 65 55 байт

Рекурсивная версия, основанная на ответе L3viathan , использующая 012как LS*:

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

Попробуйте онлайн!

Python 3 , 65 59 байт

Рекурсивное решение с использованием L, Sи *:

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

Работает через строку с фронта, и заменяет все экземпляры LSсL*

Попробуйте онлайн!

PHP, 82 байта, линейное время

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

Перебирает ввод справа налево и заменяет каждый символ типом.

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

Вычисляет тип с учетом текущего и предыдущего символа (-1 или 1). Если равно, тип не меняется.

PHP , 70 байт

L = 1, S = 0, * = 2

Многобайтовая поддержка необходима для последнего Тестового случая с §+3 байтами mb_substrвместоsubstr

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

Попробуйте онлайн!

PHP , 71 байт

L = 1, S = 0, * = 2

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

Попробуйте онлайн!

PHP , 74 байта

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

Попробуйте онлайн!