Просмотр кода страницы Проект:Хорошие статьи/Кандидаты/6 апреля 2020

{{КХС-Навигация}}
== [[Суффиксный автомат]] ==
{{закрыто}}
Статья про незаслуженно малопопулярную (по сравнению с [[суффиксное дерево]]) строковую структуру данных. Понемногу расширял с лета, надеюсь довести до ИС, но решил сперва всё же сюда. Ещё вижу потенциал для расширения, но уже сейчас, на мой взгляд, статья достаточно подробно раскрывает основные моменты. Статья была на [[Википедия:Рецензирование/Суффиксный автомат|рецензировании]]. <span style="font:111% Helvetica Neue">'''adamant.pwn'''</span> — <small>[[Служебная:Вклад/adamant.pwn|contrib]]/[[ОУ:adamant.pwn|talk]]</small> 16:37, 6 апреля 2020 (UTC)
=== За ===
# {{За}}. Грандиозно! Если всё остальное читатель и не поймёт, то благодаря пояснениям в таблице с рисунками «Построение суффиксного автомата для слова abbcbc» есть шанс на какое-то интуитивное понимание. Возвращаясь к этой центральной, на мой взгляд, последовательности иллюстраций, гвоздю статьи в разделе [[Суффиксный автомат#Изменение переходов и суффиксных ссылок|Изменение переходов и суффиксных ссылок]]… В левой или верхней части каждой ячейки у нас «суффиксный автомат», а в правой или нижней части — «дерево суффиксных ссылок». Читателю будет легче воспринять эту разницу, если все автоматы или все деревья в этой таблице будут другого, не чёрного цвета. Например, автоматы чёрные, а деревья зелёные или коричневые. --[[У:AKA MBG|Andrew Krizhanovsky]] ([[ОУ:AKA MBG|обс.]]) 04:34, 11 мая 2020 (UTC)

=== Против ===
=== Комментарии ===
* Выглядит неплохо. Только почему б авторов в верхнем шаблоне не вписать шаблоном НП5? — [[У:Muhranoff|Muhranoff]] ([[ОУ:Muhranoff|обс.]]) 08:58, 7 апреля 2020 (UTC)
** Потому что они подгружаются с викидаты… <span style="font:111% Helvetica Neue">'''adamant.pwn'''</span> — <small>[[Служебная:Вклад/adamant.pwn|contrib]]/[[ОУ:adamant.pwn|talk]]</small> 10:39, 7 апреля 2020 (UTC)
*** Так потому и подгружаются, что не вписаны. — [[У:Muhranoff|Muhranoff]] ([[ОУ:Muhranoff|обс.]]) 14:33, 7 апреля 2020 (UTC)
**** Ну, по мне викификация на викиданные это не такая уж и проблема, но так и быть — вписал через iw5. <span style="font:111% Helvetica Neue">'''adamant.pwn'''</span> — <small>[[Служебная:Вклад/adamant.pwn|contrib]]/[[ОУ:adamant.pwn|talk]]</small> 16:22, 7 апреля 2020 (UTC)
* Историю лучше переименовать в исторический очерк и поместить ближе к концу. В начале статьи вообще непонятно о чём речь, имена и даты не имеют смысла. — [[У:Zanka|Zanka]] ([[ОУ:Zanka|обс.]]) 11:57, 7 апреля 2020 (UTC)
** Ну не знаю, вроде бы обычно такие разделы всё таки идут в начале статьи и называются «история»… См. [[Алгоритм Евклида]], например. Или тот же [[Алгоритм Шрайера — Симса]]. <span style="font:111% Helvetica Neue">'''adamant.pwn'''</span> — <small>[[Служебная:Вклад/adamant.pwn|contrib]]/[[ОУ:adamant.pwn|talk]]</small> 12:09, 7 апреля 2020 (UTC)
* В определении слова неясно предназначение k (в смысле ясно, но оно там лишнее, в формуле слова k нет). — [[У:Zanka|Zanka]] ([[ОУ:Zanka|обс.]]) 11:57, 7 апреля 2020 (UTC)
** Убрал. <span style="font:111% Helvetica Neue">'''adamant.pwn'''</span> — <small>[[Служебная:Вклад/adamant.pwn|contrib]]/[[ОУ:adamant.pwn|talk]]</small> 12:36, 7 апреля 2020 (UTC)
* В конце раздела Основные обозначения стоит точка с запятой, а перед словом соответственно не хватает запятой. — [[У:Zanka|Zanka]] ([[ОУ:Zanka|обс.]]) 11:57, 7 апреля 2020 (UTC)
** Заменил на точку. Зачем перед словом соответственно запятая не понял, это ведь не переход от одной части предложения к другой... <span style="font:111% Helvetica Neue">'''adamant.pwn'''</span> — <small>[[Служебная:Вклад/adamant.pwn|contrib]]/[[ОУ:adamant.pwn|talk]]</small> 12:36, 7 апреля 2020 (UTC)
* Формулировку кортежа лучше дать в другом порядке, для тех кто в математику заглядывает изредка, как я, а не находится в ней 24/7. Сначала обозначить все элементы, а потом сказать, что они задают суффиксный автомат. В чистом виде поменять местами предложени не получится, нужно чуть-чуть больше править. — [[У:Zanka|Zanka]] ([[ОУ:Zanka|обс.]]) 11:57, 7 апреля 2020 (UTC)
** Попробовал расписать подробнее. Так лучше? <span style="font:111% Helvetica Neue">'''adamant.pwn'''</span> — <small>[[Служебная:Вклад/adamant.pwn|contrib]]/[[ОУ:adamant.pwn|talk]]</small> 12:36, 7 апреля 2020 (UTC)
* Непонятно, в каком месте заканчивается конечный автомат и начинается суффиксный. Ну то есть начиная с какого-то места говорится уже про суффиксный автомат, но определение непонятно. — [[У:Zanka|Zanka]] ([[ОУ:Zanka|обс.]]) 11:57, 7 апреля 2020 (UTC)
** Попробовал выделить более явно. Про суффиксный автомат начинаем говорить с «В таких обозначениях, суффиксный автомат — это минимальный ДКА…». <span style="font:111% Helvetica Neue">'''adamant.pwn'''</span> — <small>[[Служебная:Вклад/adamant.pwn|contrib]]/[[ОУ:adamant.pwn|talk]]</small> 12:36, 7 апреля 2020 (UTC)
* В состоянии автомата появляется буква R, неопределённая ранее. — [[У:Zanka|Zanka]] ([[ОУ:Zanka|обс.]]) 11:57, 7 апреля 2020 (UTC)
** Речь про <math>[\omega]_R</math>? Ну, она соответствует слову «right», это следует явно прописать? <span style="font:111% Helvetica Neue">'''adamant.pwn'''</span> — <small>[[Служебная:Вклад/adamant.pwn|contrib]]/[[ОУ:adamant.pwn|talk]]</small> 12:36, 7 апреля 2020 (UTC)
* Правый конец и правый контекст - это одно и то же или нет? Если нет, то что тогда правый конец? В любом случае хорошо бы это уточнить в статье. — [[У:Zanka|Zanka]] ([[ОУ:Zanka|обс.]]) 11:57, 7 апреля 2020 (UTC)
** Исправил на «правую позицию» и добавил про это в «основные обозначения». Теперь понятнее? <span style="font:111% Helvetica Neue">'''adamant.pwn'''</span> — <small>[[Служебная:Вклад/adamant.pwn|contrib]]/[[ОУ:adamant.pwn|talk]]</small> 12:36, 7 апреля 2020 (UTC)
* Последняя формула первой леммы меня смущает. Там вроде как длина слова, как она может принадлежать множеству правых концов? Вроде как размерности разные получаются. — [[У:Zanka|Zanka]] ([[ОУ:Zanka|обс.]]) 11:57, 7 апреля 2020 (UTC)
** Всё в порядке -- правая позиция вхождения это число, разность <math>n</math> и длины слова -- тоже. <span style="font:111% Helvetica Neue">'''adamant.pwn'''</span> — <small>[[Служебная:Вклад/adamant.pwn|contrib]]/[[ОУ:adamant.pwn|talk]]</small> 12:36, 7 апреля 2020 (UTC)
* Там где "суффиксные ссылки образуют дерево", не знаю, есть ли у нас статьи, но дерево, вершины и рёбра хорошо бы викифицировать. И в "такие что" должна быть запятая. — [[У:Zanka|Zanka]] ([[ОУ:Zanka|обс.]]) 11:57, 7 апреля 2020 (UTC)
** Викифицировал. <span style="font:111% Helvetica Neue">'''adamant.pwn'''</span> — <small>[[Служебная:Вклад/adamant.pwn|contrib]]/[[ОУ:adamant.pwn|talk]]</small> 12:37, 7 апреля 2020 (UTC)

Я попробую дальше почитать, но уровень математики не мой, могут быть слишком глупые вопросы. — [[У:Zanka|Zanka]] ([[ОУ:Zanka|обс.]]) 11:57, 7 апреля 2020 (UTC)

==== Алгоритм ====
Напишу здесь несколько пожеланий к разделу "Алгоритм".
# Предлагаю дать название алгоритму и разделу. То есть не просто "Алгоритм", а например "Алгоритм построения суффиксного автомата".
# В дополнение к ссылке "Crochemore, Hancart, 1997, pp. 31—36" можно сослаться на конкретную страницу PDF файла с помощью конструкции #page=34 вот так: [https://hal-upec-upem.archives-ouvertes.fr/hal-00620792/document#page=34].

Правильно я понял, что Ваш алгоритм в разделе «Алгоритм» — это Ваша интерпретация псевдокода [https://hal-upec-upem.archives-ouvertes.fr/hal-00620792/document#page=34 Fig. 7.4 и Fig. 7.5]? Если это так, то…

3) Попробуйте, пожалуйста, привести (кроме текстового описания и программы на С++, которые уже есть в разделе) также и псевдокод. 
Псевдокод популярен, поскольку он позволяет компактно описать то, что текстом выливается в целую портянку или простыню :) 
В идеале нумерация строк псевдокода совпадает с нумерацией текстового алгоритма.

4) Укажите, пожалуйста, входные параметры и результат алгоритма (что возвращает алгоритм). У них (Fig. 7.4 и Fig. 7.5) это указано.

Третье пожелание самое сложное в реализации и самое важное, чтобы читателей, понявших статью, стало на N+1 больше :) --[[У:AKA MBG|Andrew Krizhanovsky]] ([[ОУ:AKA MBG|обс.]]) 15:27, 26 апреля 2020 (UTC)
* Сделал, за исключением прямой сноски на страницу. Ссылка с {{code|<nowiki>#page=34</nowiki>}}, кажется, не очень сочетается с форматом {{tl|sfn-текст}}, который используется в статье для оформления сносок, так как они могут напрямую ссылаться только на развёрнутый текст в разделе «Литература». <span style="font:111% Helvetica Neue">'''adamant.pwn'''</span> — <small>[[Служебная:Вклад/adamant.pwn|contrib]]/[[ОУ:adamant.pwn|talk]]</small> 18:51, 26 апреля 2020 (UTC)
* В «префиксом, суффиксом и подсловом» — может, переставить в альфа-бета-гамма, а то глаз спотыкается?{{pb}}«Формально, детерминированный конечный автомат» — разве в разделе есть что-то от детерминированности?{{pb}}К моменту «важное утверждение о минимальных автоматах» нигде не определяется, что такое минимальный автомат. [[У:Wikisaurus|Викизавр]] ([[ОУ:Wikisaurus|обс.]]) 17:35, 30 апреля 2020 (UTC)
** Исправил определение, чтоб соответствовало детерминированности, минимальный автомат определил. Альфа-бета-гамма здесь нежелательны, хочется сделать акцент на префиксе и суффиксе. <span style="font:111% Helvetica Neue">'''adamant.pwn'''</span> — <small>[[Служебная:Вклад/adamant.pwn|contrib]]/[[ОУ:adamant.pwn|talk]]</small> 19:49, 30 апреля 2020 (UTC)

==== Лемма, определяющая [[взаимно-однозначное соответствие]] ====

Цитата из статьи:

Это позволяет сформулировать следующую лемму, определяющую [[взаимно-однозначное соответствие]] между правым контекстом слова и множеством позиций его вхождений в <math>S</math> в качестве подслова:

{{Теорема|Пусть <math>endpos(\omega)=\{r: \omega=s_l \dots s_r \}</math> — множество правых позиций вхождений <math>\omega</math> в <math>S</math>. 

Между элементами множеств <math>endpos(\omega)</math> и <math>[\omega]_R</math> есть следующее взаимно однозначное соответствие:
* Если <math>x \in endpos(\omega)</math>, то <math>s_{x+1}s_{x+2}\dots s_n \in [\omega]_R</math>;
* Если <math>\alpha \in [\omega]_R</math>, то <math>n-\vert\alpha\vert \in endpos(\omega)</math>.}}

Конец цитаты.

Хочу понять лемму. Понял, что endpos(w) — это множество чисел, позиций слова w в строке S. <s>Не понял, что такое l и r в первой строке леммы.</s> (l и r понял).

Хорошо бы примерчик в статью. Например, пусть S="кот ел антрекот" (15 символов), w="кот". Чему тогда равно по этой лемме endpos("кот")=? и 
<math>[\omega]_R</math>? --[[У:AKA MBG|Andrew Krizhanovsky]] ([[ОУ:AKA MBG|обс.]]) 15:27, 26 апреля 2020 (UTC)

: <math>endpos(\text{``кот''})=\{3, 15\}</math> (если нумерация символов в строке идёт с единицы). Правильно? Осталось с <math>[\omega]_R</math> разобраться... --[[У:AKA MBG|Andrew Krizhanovsky]] ([[ОУ:AKA MBG|обс.]]) 15:35, 26 апреля 2020 (UTC)
* Добавил пример и уточнение. <span style="font:111% Helvetica Neue">'''adamant.pwn'''</span> — <small>[[Служебная:Вклад/adamant.pwn|contrib]]/[[ОУ:adamant.pwn|talk]]</small> 19:00, 26 апреля 2020 (UTC)
:* Отлично! Теперь хочется довести пример до логического конца, то есть приведём пример для последних двух строчек леммы. Вы дали чёткий и ясный пример: 

 Например, для слова <math>abacaba</math> и его подслова <math>ab</math> выполнено <math>endpos(ab)=\{2,6\}</math> и <math>[ab]_R = \{acaba, a\}</math>. (и неформальное пояснение)

Предлагаю вначале этого примера написать:  <math>S = a_{1}b_{2}a_{3}c_{4}a_{5}b_{6}a_{7}</math> (индекс указывает номер символа).

Продолжаем пример. Если <math>x=2 \in endpos(ab)</math>, то положим <math>s_{x+1}s_{x+2}\dots s_n = a_{3}c_{4}a_{5}b_{6}a_{7} = acaba \in [\omega]_R</math>.

Если <math>\alpha = \text{acaba} \in [\omega]_R</math>, то положим <math>n-\vert\alpha\vert = 7 - \vert\text{acaba}\vert=7-5=2 \in endpos(\omega)</math>.

Буду признателен, если Вы простите мне, что я так разжёвываю материал, который Вам очевиден. Мне кажется, что рядовым читателям с такими примерами будет понятнее.

По оформлению. Вот бы разместить параллельно лемму и пример. Это компактно и наглядно. Попробую сделать так.

{| class="wikitable"
|+ Лемма <math>endpos(\omega) \leftrightarrow [\omega]_R</math>
|-
! Лемма !! Пример, дано слово <math>S = a_{1}b_{2}a_{3}c_{4}a_{5}b_{6}a_{7}</math> и подслово <math>ab</math>
|-
| Пусть <math>endpos(\omega)=\{r: \omega=s_l \dots s_r \}</math> — множество правых позиций вхождений <math>\omega</math> в <math>S</math>. 
|| <!-- Пример -->
<math>endpos(ab)=\{2,6\} \leftrightarrow [ab]_R = \{acaba, a\}</math>

|-
| Между элементами множеств <math>endpos(\omega)</math> и <math>[\omega]_R</math> есть следующее взаимно однозначное соответствие:
|| <!-- Пример (пустая ячейка) -->
 
|-
| * Если <math>x \in endpos(\omega)</math>, то <math>s_{x+1}s_{x+2}\dots s_n \in [\omega]_R</math>;
|| <!-- Пример -->
Если <math>x=2 \in endpos(ab)</math>, то положим <math>s_{x+1}s_{x+2}\dots s_n = a_{3}c_{4}a_{5}b_{6}a_{7} = acaba \in [\omega]_R</math>.

|-
| * Если <math>\alpha \in [\omega]_R</math>, то <math>n-\vert\alpha\vert \in endpos(\omega)</math>.
|| <!-- Пример -->
Если <math>\alpha = \text{acaba} \in [\omega]_R</math>, то положим <math>n-\vert\alpha\vert = 7 - \vert\text{acaba}\vert=7-5=2 \in endpos(\omega)</math>.
|}

(Мелочь: "взаимно однозначное" сейчас в статье встречается раздельно и через дефис. Выберите что-то одно, пожалуйста.)

Я позволил себе в заголовке таблицы дать лемме название в виде формулы. Не настаиваю на таком названии.

Если содержательно согласны с этой таблицей, то для оформления таблицы нужно сообразить, как убрать горизонтальные линии в таблице, чтобы и лемма, и пример были целостными. Можно фон убрать у леммы. Можно убрать линии таблицы вокруг столбца с примером, оставить рамку только вокруг леммы, как было в оригинале. --[[У:AKA MBG|Andrew Krizhanovsky]] ([[ОУ:AKA MBG|обс.]]) 07:46, 27 апреля 2020 (UTC)
* Дополнил чуть более подробным описанием. Думаю, параллельно отображать лемму и пример не следует, т. к. такое оформление не используется с другими утверждениями, обрамлёнными в {{tl|теорема}}. <span style="font:111% Helvetica Neue">'''adamant.pwn'''</span> — <small>[[Служебная:Вклад/adamant.pwn|contrib]]/[[ОУ:adamant.pwn|talk]]</small> 18:09, 27 апреля 2020 (UTC)
:* Спасибо, что дополнили пример. 
:* Жаль, что не взяли параллельный пример к лемме. Аргумент за единообразие всех теорем понятен, но мы можем и для других лемм/теорем подумать над примерами :) --[[У:AKA MBG|Andrew Krizhanovsky]] ([[ОУ:AKA MBG|обс.]]) 12:32, 28 апреля 2020 (UTC)

==== Структурные свойства состояний суффиксного автомата и его слов ====

Цитата: 

Из этого следует ряд структурных свойств состояний суффиксного автомата и слов, которые ими принимаются. Пусть <math>|\alpha| \leq |\beta|</math>, тогда:
* Если у <math>[\alpha]_R</math> и <math>[\beta]_R</math> есть хотя бы один общий элемент <math>x</math>, то <math>\alpha</math> — суффикс <math>\beta</math> и, как следствие, <math>endpos(\beta) \subset endpos(\alpha)</math> и <math>[\beta]_R \subset [\alpha]_R</math>;

Конец цитаты.

Предлагаю такой текст для примера:

В качестве примера возьмём то же <math>S = abacaba</math>, положим <math>\alpha = ab</math> (чтобы использовать предыдущий пример) и <math>\beta = cab</math>, то получим:
* <math>|\alpha| = |ab| \leq |cab| = |\beta|</math>;
* <math>[ab]_R = \{acaba, a\}</math> (см. предыдущий пример);
* <math>[cab]_R = \{a\}</math>;

Здесь общим элементом <math>[ab]_R</math> и <math>[cab]_R</math> является  <math>x = a</math>, при этом <math>\alpha = ab</math> является суффиксом <math>\beta = cab</math>.

Конец текста для примера.

Замечания:
# Не слишком ли простой получился пример и слишком короткое <math>x = a</math> (из одного символа)? Хотя, может, пример и должен быть простым.
# Для меня чудо и фокус состоит в том, что при общем иксе, <math>\alpha</math> оказалось суффиксом <math>\beta</math>. Доказывается ли это строго? Или это очевидно? --[[У:AKA MBG|Andrew Krizhanovsky]] ([[ОУ:AKA MBG|обс.]]) 13:24, 28 апреля 2020 (UTC)
* Давайте сразу уточним — вы сейчас хотите оснастить примером все утверждения в тексте? По поводу последнего — если у двух строк совпадает одна из правых позиций вхождений в строку, то более короткая является суффиксом более длинной. В общем, да, это очевидное свойство. Это примерно равносильно тому, что если <math>\alpha</math> и <math>\beta</math> являются суффиксами третьей строки <math>S</math>, то одна из них — суффикс другой. Возможно, пропущенная мысль тут в том, что если у <math>[\alpha]_R</math> и <math>[\beta]_R</math> есть общий элемент, то он есть и у <math>endpos(\alpha)</math> и <math>endpos(\beta)</math>, по доказанному выше. <span style="font:111% Helvetica Neue">'''adamant.pwn'''</span> — <small>[[Служебная:Вклад/adamant.pwn|contrib]]/[[ОУ:adamant.pwn|talk]]</small> 13:51, 28 апреля 2020 (UTC)
:* Мне думается, что примеры облегчают понимание читателям. Если бы тема и текст были проще, рецензентов было бы куда больше. Позволю себе пригласить к чтению статьи математика @[[Участник:Tosha]]. Чегой-то я кроме Занки и Тоши не вспоминаю математиков в рувики, хотя они, конечно, есть и просто ждут приглашения сюда (я сам случайно на эту номинацию наткнулся, к счастью или несчастью номинатора). 
:* adamant.pwn, Вы пишите про возможную "пропущенную мысль". Может её стоит добавить в статью со ссылкой на предыдущую лемму? --[[У:AKA MBG|Andrew Krizhanovsky]] ([[ОУ:AKA MBG|обс.]]) 07:40, 30 апреля 2020 (UTC)
:** Мне просто кажется, что было бы удобнее и быстрее сразу обозначить все места, где хочется иметь более подробные пояснения, чтоб работать с ними параллельно, а не последовательно. А приглашение к рецензированию — оно на [[Проект:Математика]] висит, только мне кажется, что в нашем разделе обычно другими разделами математики интересуются, потому и данная номинация не очень популярна. В целом, я в последнее время стараюсь не очень усердствовать с примерами в статьях, так как это может вызвать реакция вида «пример — это оригинальное исследование» или «нет в АИ — не нужно нести в статью» со стороны ряда участников. А в статусных проектах эти примеры ещё и образуют абзацы без сносок, что здесь вообще как красная тряпка… <span style="font:111% Helvetica Neue">'''adamant.pwn'''</span> — <small>[[Служебная:Вклад/adamant.pwn|contrib]]/[[ОУ:adamant.pwn|talk]]</small> 07:51, 30 апреля 2020 (UTC)
:::* Аргумент про опасение обвинений из-за примеров понял. Думаю, что случай с кандидатами в статусные статьи особый в том, что есть обсуждение и решение нескольких участников. Если продолжить линию опасений, то придётся отказаться от исходных кодов, иллюстрирующих алгоритмы, если их нет в АИ.
:::* Параллельно, к сожалению, не могу. Вы уже догадались, что у меня в голове однопроцессорная устаревшая модель :) Поэтому я пишу замечания по ходу чтения текста. --[[У:AKA MBG|Andrew Krizhanovsky]] ([[ОУ:AKA MBG|обс.]]) 08:04, 30 апреля 2020 (UTC)
:::** Да, исходный код на самом деле [[Википедия:Оформление статей/Статьи об информационных технологиях#Оформление листингов в статьях об алгоритмах|нежелателен]], особенно если в статье есть псевдокод, я его убрал. <span style="font:111% Helvetica Neue">'''adamant.pwn'''</span> — <small>[[Служебная:Вклад/adamant.pwn|contrib]]/[[ОУ:adamant.pwn|talk]]</small> 19:56, 30 апреля 2020 (UTC)
* Дополнил. <span style="font:111% Helvetica Neue">'''adamant.pwn'''</span> — <small>[[Служебная:Вклад/adamant.pwn|contrib]]/[[ОУ:adamant.pwn|talk]]</small> 09:36, 30 апреля 2020 (UTC)
:* Спасибо! --[[У:AKA MBG|Andrew Krizhanovsky]] ([[ОУ:AKA MBG|обс.]]) 12:49, 30 апреля 2020 (UTC)

==== Ох уж эта гамма ====

Вы пишите третье структурное свойство:
* Если <math>[\alpha]_R=[\beta]_R</math> и <math>\gamma</math> — суффикс <math>\beta</math>, такой что <math>|\alpha| \leq |\gamma| \leq |\beta|</math>, то <math>[\alpha]_R = [\gamma]_R = [\beta]_R</math>.

А вы можете привести такой пример гаммы не равной бете по длине, чтобы <math>[\alpha]_R = [\gamma]_R = [\beta]_R</math>? Мне кажется, что если <math>[\alpha]_R = [\gamma]_R = [\beta]_R</math>, то <math>|\alpha| = |\gamma| = |\beta|</math>. --[[У:AKA MBG|Andrew Krizhanovsky]] ([[ОУ:AKA MBG|обс.]]) 13:24, 28 апреля 2020 (UTC)
* Да, конечно. Строка <math>S=abc</math>, подстроки <math>\alpha=c</math>, <math>\gamma=bc</math> и <math>\beta = abc</math>. Здесь <math>[\alpha]_R = [\beta]_R = [\gamma]_R = \{\varepsilon \}</math>. <span style="font:111% Helvetica Neue">'''adamant.pwn'''</span> — <small>[[Служебная:Вклад/adamant.pwn|contrib]]/[[ОУ:adamant.pwn|talk]]</small> 13:45, 28 апреля 2020 (UTC)
:* Правильно я понял, что если исключить пустое слово <math>\varepsilon</math> как особый случай, то привести пример [[wikt:навскидку|навскидку]] для третьего структурного свойства не получится? --[[У:AKA MBG|Andrew Krizhanovsky]] ([[ОУ:AKA MBG|обс.]]) 06:52, 30 апреля 2020 (UTC)
:** Неправильно. <math>S=abcd</math>, но <math>\alpha,\gamma,\beta</math> — те же самые. Тогда <math>[\alpha]_R = [\beta]_R = [\gamma]_R = \{d\}</math>. <span style="font:111% Helvetica Neue">'''adamant.pwn'''</span> — <small>[[Служебная:Вклад/adamant.pwn|contrib]]/[[ОУ:adamant.pwn|talk]]</small> 07:13, 30 апреля 2020 (UTC)
:::* Спасибо! --[[У:AKA MBG|Andrew Krizhanovsky]] ([[ОУ:AKA MBG|обс.]]) 07:41, 30 апреля 2020 (UTC)

==== Приглашение для математиков ====
Уважаемые коллеги, @{{u|Agor153}}, @{{u|Arventur}}, @{{u|colt_browning}}, @{{u|Irina Gelbukh}}, @{{u|Jumpow}}, @{{u|Sim3331621}}. Я видел, что вы редактировали статьи по математике. Поэтому приглашаю к рецензированию статьи [[Суффиксный автомат]]. Если такие уведомления неинтересны, напишите мне, пожалуйста. Постараюсь больше не беспокоить. --[[У:AKA MBG|Andrew Krizhanovsky]] ([[ОУ:AKA MBG|обс.]]) 07:57, 30 апреля 2020 (UTC)

==== Левое расширение ==== 

Цитата:

''Левым расширением'' <math>\overset{\scriptstyle{\leftarrow}}{\gamma}</math> строки <math>\gamma</math> называют самую длинную строку <math>\omega</math>, имеющую тот же правый контекст, что и <math>\gamma</math>. Длину <math>|\overset{\scriptstyle{\leftarrow}}{\gamma}|</math> самой длинной строки, принимаемой состоянием <math>q=[\gamma]_R</math>, обозначают как <math>len(q)</math>.

: Например, для слова <math>S=abacaba</math> и правого контекста <math>[ab]_R = \{acaba, a\}</math> имеем, что подслово <math>\omega=ab</math> нельзя расширить, не потеряв элементы правого контекста, поэтому <math>len(q) = max \{|acaba|, |a| \} = max \{5, 1\} = 5</math>.

Верно ли я понял, как вычисляют длину q? --[[У:AKA MBG|Andrew Krizhanovsky]] ([[ОУ:AKA MBG|обс.]]) 18:02, 1 мая 2020 (UTC)
* Нет, в данном случае мы смотрим на все слова, у которых правый контекст равен <math>\{acaba, a\}</math>. Нас интересует длина наибольшего такого слова, то есть, <math>len(q) = |\overset{\leftarrow}{b}| = |\overset{\leftarrow}{ab}| = |ab| = 2</math>. <span style="font:111% Helvetica Neue">'''adamant.pwn'''</span> — <small>[[Служебная:Вклад/adamant.pwn|contrib]]/[[ОУ:adamant.pwn|talk]]</small> 18:10, 1 мая 2020 (UTC)
:* Теперь понял. Спасибо! --[[У:AKA MBG|Andrew Krizhanovsky]] ([[ОУ:AKA MBG|обс.]]) 13:36, 2 мая 2020 (UTC)

==== Пример построения ====

В статье на русском языке [https://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D1%83%D1%84%D1%84%D0%B8%D0%BA%D1%81%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82] есть раздел "Пример построения". Думаю, что подобный раздел в нашей статьи был бы уместен и полезен. Возможно, для другой строки. По оформлению вполне устраивает таблица: слева рисунок и справа описание для каждого шага. --[[У:AKA MBG|Andrew Krizhanovsky]] ([[ОУ:AKA MBG|обс.]]) 17:12, 4 мая 2020 (UTC)
* Мне бы не очень хотелось занимать таким примером много вертикального места. Для иллюстрации, мне кажется, более-менее достаточно одного отдельного шага, изображённого на «Изменения в суффиксных структурах при приписывании одного символа». Меня бы устроило оформить это в виде встроенного слайд-шоу или таблицы с вкладками, но я не уверен, как это наилучшим образом технически реализовать. <span style="font:111% Helvetica Neue">'''adamant.pwn'''</span> — <small>[[Служебная:Вклад/adamant.pwn|contrib]]/[[ОУ:adamant.pwn|talk]]</small> 08:35, 8 мая 2020 (UTC)
:* Таблица не будет занимать места,  если она по умолчанию свёрнута. Вот документация: [[Википедия:Таблицы#Сворачиваемая]]. --[[У:AKA MBG|Andrew Krizhanovsky]] ([[ОУ:AKA MBG|обс.]]) 18:36, 8 мая 2020 (UTC)
:** Нет, так она будет заниматься много места если развернуть. Сделал под это дело [[Шаблон:Слайд-шоу]]. Осталось понаделать картинок… <span style="font:111% Helvetica Neue">'''adamant.pwn'''</span> — <small>[[Служебная:Вклад/adamant.pwn|contrib]]/[[ОУ:adamant.pwn|talk]]</small> 18:32, 9 мая 2020 (UTC)
:** Добавил. <span style="font:111% Helvetica Neue">'''adamant.pwn'''</span> — <small>[[Служебная:Вклад/adamant.pwn|contrib]]/[[ОУ:adamant.pwn|talk]]</small> 23:13, 9 мая 2020 (UTC)
{{закрыто-конец}}

=== Итог ===
Статья требованиям соответствует, проведена большая работа по замечаниям. Статус присвоен, рекомендую номинировать на КИС. — [[У:Zanka|Zanka]] ([[ОУ:Zanka|обс.]]) 20:50, 16 мая 2020 (UTC)