Комментарии 11
Алгоритм-алгоритмом, но подскажите, где это полезно "на практике", какие проблемы может решить?
Вашими книгами резать картошку неудобно. Запретите книги! И ты, конечно, не заметил, что такой палиндром можно уменьшить в 2 раза.
Где используется - шифрование, криптография, сжатия данных, обработка сигналов.
Ну, котики тоже проблем особо не решают, однако ж их фотографиями завален весь интернет...
Отмечу, впрочем, подобный алгоритм (в смысле, тоже с неочевидным быстрым решением, емнип до него додумались только в 80-х), но реально используемый: поиск бегущего максимума (максимум по N точкам, соседним с текущей).
Поиск шпилек в геномных последовательностях, там, правда, антипалиндромы, и неточные.
Если идти по строке слева на право и искать паттерн AXA или AA, где А - это любой символ, то можно находить центры палиндромов и уже от центров идти в обе стороны к краям определят максимальную длинну. Так по идее должно иметь сложность от O(N) до O(N*N) в худшем случае.
Статье отчаянно не хватает двух вещей:
1. Код для наивного и промежуточного решений. Они описаны так, что не решавший задачу человек вынужден будет её практически решать при чтении в уме.
2. Нормальных наименований в коде. Я понимаю, что код писался в олимпиадном стиле, когда почти все переменные однобуквенные, но выкладывать такой код в статье - позор.
P.s. Замечу, что даже при отсутствии данных вещей в оригинале, имело немалый смысл добавить их при переводе как ремарки.
Вы прям как в том анекдоте: во-первых, официант, что за дрянь вы мне принесли? во-вторых, почему так мало? :D
Давайте по пунктам:
По моему мнению, псевдокода вполне достаточно. Акцент статьи на конкретном методе. Остальные приведены для справки. Моя задача была сделать статью как можно короче, чтобы не пугать читателя объёмом (как в остальных 100500 источниках по теме).
Если вам нужен обфусцированный олимпиадный стиль, читайте русскую википедию https://ru.wikipedia.org/wiki/Поиск_длиннейшей_подстроки-палиндрома
если нужен код с многобуквенными переменными на несколько экранов, читайте английскую википедию
https://en.wikipedia.org/wiki/Longest_palindromic_substringМне оба этих изложения показались непонятными, поэтому и написал свою статью, где было бы на пальцах и в картинках изложено, что же там на самом деле происходит.
А позор это:
Считать, что все должны писать код том стиле, к которому вы привыкли.
Ожидать, что переводчик будет переписывать код, а кроме того (но это уже не к вам)
Переводить статьи без согласия (хотя бы уведомления!) автора.
Если я правильно понял, то Вы автор оригинала.
Так вот,
В статье нет псевдокода других решений, здесь есть вот это:
ЦИКЛ по символам всей строки:
ЦИКЛ по всем длинам, начиная с текущего символа:
ЦИКЛ по символам в этой подстроке:Для человека, который не писал сравнительно недавно этот алгоритм и не занимается им постоянно, это не даёт вообще никакой информации.
Вы, кажется, вообще не поняли мой второй пункт, судя по Вашему ответу. Моя претензия ровно в том, что Вы используете обфусцированный олимпиадный стиль. Даже специально на русскую википедию заглянул. простите, отличий в стиле я не вижу, всё также вырвиглазно. Кажется, практически всё сообщество программистов уже очень давно пришло к пониманию того, что олимпиадный стиль - чудовищно плохой. И подходит только и исключительно для олимпиад и быстрого (в пределах часов) прототипирования. И уж точно такой стиль никак не подходит для публикаций. Прошу простить мою резкость, но с самых университетских времён каждый грёбаный преподаватель и автор книг/статей на русском языке считает своим долгом заставить читателя самостоятельно разбираться, что и какая буковка в коде обозначает, в итоге 3/4 времени тратится не на понимание алгоритма, а на понимание смысла однобуквенных переменных автора. И да, английская википедия - отличный пример как надо делать.
Ещё раз простите за резкость, боюсь, это Вас задело. Это просто очень наболевшее. Как очереди в поликлиниках и мфц. Надеюсь, Вы примете к сведению, что для восприятия со стороны ученика/читателя однобуквенный олимпиадный стиль чрезвычайно неудобен.
По поводу перевода статей - возможно, это уже Вы исправили, но в шапке есть ссылка на Вашу оригинальную статью. Если изначально этой ссылки не было - искренне присоединяюсь к осуждению переводчика
Спасибо за статью!))
Не самый простой алгоритм для восприятия, но с помощью вашей статьи смогла осознать "как же сей зверь работает"))
В каких-то моментах хочется чуть больше пояснений "для тупых", по типу "что такое C-(i-C) и почему именно так", возможно с примерами, тк ифы, описывающие вхождения - мне показались самой сложной частью.
Но, в целом, статья прекрасна и особенно иллюстрации, которые вы приложили - помогают разобраться!)
Алгоритм поиска самой длинной подстроки-палиндрома