Привет! Читаю про префикс-функцию на e-maxx и не могу понять пункт про сжатие строки. А именно, из чего следует в части где n не делится на k, что все буквы блока совпадают? В примере на картинке это очевидно. А что если у нас сдвиг суффикса относительно второго блока будет больше чем на 1 символ?
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
3 дня
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
3 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 2 | maomao90 | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 20.11.2024 10:24:14 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
Это следует из каких-то заблуждений. Вот пример строки из 20 символов:
В обозначениях e-maxx: k = 8 и пусть p = 10, тогда si = si + 2.
Спасибо за ответ!
Но я не думаю, что здесь стоит использовать реальный пример. Во-первых, период p (в приведённом примере), очевидно, периодом не является. Если предположить, что утверждение 'если n не делится k, тогда сжатия не существует' верно, то реального примера и не получится привести. Поэтому, думаю, следует уйти от реальных примеров к абстрактным.
Ну или привести контрпример в котором, существует период p при заданных условиях:)
Если я неправильно Вас понял, поправьте, пожалуйста.
Можно абстрагироваться так: воспринимайте цифры в строке не как символы, а как s1, s2, ..., s8. Мы пользуемся повторяющейся нумерацией, потому что нам известна длина строки (20) и значение префикс-функции для последней позиции (12), откуда следует, что si = si + 8. Тогда предположив, что p является периодом строки, мы получаем, что еще и si = si + 2 (по картинке). Но мы не получаем si = si + 1, как написано на e-maxx.
Но тогда p не ответ и префикс функция посчитана неверно получается.
Ну да, в этом и состоит смысл доказательства от противного) Мы же не теорему опровергаем, а просто указываем на ошибку в доказательстве на e-maxx и отвечаем на ваш вопрос из поста: не всегда из того, что n не делится на k следует, что все буквы блока совпадают.
Но доказательство на e-maxx опирается на то, что p ответ (то есть минимальный период). А мы же всего лишь навсего доказали, что 10 не ответ.
Доказательство в своей последней части нигде на минимальность не опирается.
Может я неверно что-то понял..
"Найти такую строку t наименьшей длины, что s можно представить в виде конкатенации одной или нескольких копий t. Понятно, что проблема является в нахождении длины искомой строки t. Зная длину, ответом на задачу будет, например, префикс строки s этой длины"
"Докажем от противного — предположим, что ответ существует, и имеет длину p"
Ну написано так в предположении, дальше-то это никак не используется.
Это, конечно, верно, что дальше нигде не используется. Тогда, наверное, лучше бы опираться. То есть нужно приводить к противоречию, что p можно уменьшить. Случай p == 1 не рассматривается, так как он очевиден.
Наверно можно доказать, что в этом случае блок p состоит из повторяющихся строк длины gcd(k, p).
Да, скорее всего так и есть. Учитывая, что суффикс заезжает на первый блок на p mod k, то величина этого "заезда" кратна gcd(k, p). Тогда можно перейти к блокам длины gcp(k, p). Остаётся лишь доказать, что все такие блоки одинаковы.
Мне удалось найти поистине удивительное доказательство этой теоремы, но поля этого блога слишком малы, чтобы его привести... Поэтому оставляю ссылку (последняя теорема).