Как стать автором
Поиск
Написать публикацию
Обновить

Комментарии 25

НЛО прилетело и опубликовало эту надпись здесь
Где нужны сами палиндромы — сложно сказать. Возможно, при анализе каких-то паттернов в последовательности ДНК может пригодиться (или это моя фантазия). А два указателя — достаточно популярная техника. Можно считать скользящее среднее в окне, да почти любые статистики в окне, если мы говорим об анализе временных рядов. Тут надо задачи конкретные смотреть, чтобы дальше разбираться. Например, можно вот это почитать algorithmica.org/tg/mergesort
Всего голосов 7: ↑5 и ↓2+3
НЛО прилетело и опубликовало эту надпись здесь

В биоинформатике не только ДНК, но и белки с аминокислотами. И вот там палиндромы могут быть запрасто.

Всего голосов 2: ↑2 и ↓0+2
НЛО прилетело и опубликовало эту надпись здесь

Белки — последовательности аминокислот. Последовательность может быть одинаковая туда и обратно.

Комментарий пока не оценивали0
НЛО прилетело и опубликовало эту надпись здесь

Конкретно этот алгоритм с палиндромом вряд ли можно применить где-либо. Сами полиндромы в биоинформатике иногда применяются, всякие задачи с заменой минимального количества символов для получения нужной подстрки — тоже. Но все вместе — вряд ли.


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

Всего голосов 3: ↑2 и ↓1+1
НЛО прилетело и опубликовало эту надпись здесь

Из статьи


A great number (26%) of different protein palindromes were found.

В протеинах палиндромы обычные, строковые.

Комментарий пока не оценивали0

Вы игре на музыкальных инструментах обучались? Практическое применение гаммам можете назвать?

Всего голосов 1: ↑1 и ↓0+1
НЛО прилетело и опубликовало эту надпись здесь

Решение подобных задач дает следующее практическое применение: тренирует умение анализировать проблему, искать пути решения, анализировать сложность, анализировать расход памяти, развивает нужные нейронных связи. У решения таких задач — огромная польза от повторений. Конкретная гамма до мажор, забавный курьез на один раз сыграть.


Подход "2 указателя" используется во многих алгоритмах, в том числе, имеющих практическое применение, о чем вам уже написал wataru.

Всего голосов 3: ↑3 и ↓0+3
НЛО прилетело и опубликовало эту надпись здесь

От даже одной задачи тоже польза. Примерно как от одной гаммы. Поэтому и задачи решают разные и гаммы разные играют, чтобы польза больше была.

Всего голосов 1: ↑1 и ↓0+1
интересная параллель с гаммами. Примерно то же самое, наверное, с геометрией, которая не вычислительная, а которой больше в школе и на математических кружках развлекаются. Сейчас уже практической пользы сравнительно мало, но вот сам процесс решения очень может завлечь (ну у меня по крайней мере так было, за всех не говорю).
Всего голосов 2: ↑2 и ↓0+2

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

Комментарий пока не оценивали0
я не говорю про начертательную геометрию и все другие практически применимые виды геометрии, скажем так. Графика та же, рендереры. Я, скорее, про список n примечательных фактов и приёмов, которые могут пригодиться «когда-нибудь в какой-нибудь задаче». Вот это вообще моя любимое — энциклопедия замечательных точек треугольника faculty.evansville.edu/ck6/encyclopedia/ETC.html
Всего голосов 1: ↑1 и ↓0+1
А почему алгоритм верный? Нету ли тут проблемы с выбором (максимального) элемента на замену?
К примеру ZYXAWA и одно изменение, должно давать подстроку длиной в 4 XAWA=>WAWA или XAXA. А с этой эвристикой не понятно что получается (если выберет Z).
Или AYAXABCSZEFGHIZJKLMNZOPQRSZ, здесь максимальные элементы это S (2 раза) и Z (4 раза). А правильная подстрока с одним изменением AYAYA.
Всего голосов 1: ↑1 и ↓0+1
Мы используем выбор наиболее частого, когда пытаемся за наименьшее число действий превратить подстроку фиксированной длины в нечётный палиндром, то есть решаем тут более ограниченную подзадачу. Далее мы используем это для проверки «можем ли за K операций сделать подстроку нечетным палиндромом», при этом мы уже пробуем двигать указатели и найти оптимум. В примере с ZYXAWA и K=1 будет происходить следующее:
когда указатель на левый элемент стоит на первом символе, то правый сможет уйти только до 3-го элемента (ZYZawa)
далее левый съезжает на Y, правый — на 4-й элемент (zYXYwa)
левый уходи на X, правый сможет отойти на последнего элемента. При этом тут мы заменим в подстроке XAWA символы на нечетных позициях на X или A — все равно, на четных самым частым является A, ничего не надо менять.
Всего голосов 1: ↑1 и ↓0+1
Не понятно… Выбор максимальных элементов происходит А. отдельно для чётных и нечётных Б. Перед второй стадий алгоритма В. Из всей первоначальной строки.
Поэтому: В первом случае (ZYXAWA) мы к примеру разыграли Z («если символов с максимальным числом вхождений несколько, то можно выбрать любой») и A. То получается сначала ZAxawa, потом zAХawa, zyZAwa, zyxAZA — самая длинная подстрока из 3 символов. А правильно 4.

Со вторым примером всё хуже, максимальные символы это S и Z. А менять то надо Y или A.
Комментарий пока не оценивали0
мы ищем самый частый элемент после каждого передвижение любого из указателей. Это не глобальное вычисление.
Всего голосов 1: ↑1 и ↓0+1
Ок, теперь картина проясняется. Если мы хотим находить самый частый элемент при каждом сдвиге «окна» то нам понадобится структура данных для получения самого частого символа — куча (или другая очередь приоритетов). И так как понадобится каждый шаг делать операций добавки и удаления то это добавит фактор O(log|E|). И решение будет O(n*log|E|). Конечно, в теорий, при |Е| константе можно и пренебречь, но при увеличение алфавита (E) или при наивной имплементаций нахождения максимума, код будет бежать очень медленно.
Всего голосов 1: ↑1 и ↓0+1
или log|W|, где W максимальная подстрока и если W<|Е|. Но так как нужны только входные параметры то W=O(n). и правильный фактор O(log(min(n,|Е|))).
Результат O(n*log(min(n,|Е|)))
Всего голосов 2: ↑2 и ↓0+2
Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2024, Habr