Количество подпалиндромов: различия между версиями
Содержимое удалено Содержимое добавлено
Leksey (обсуждение | вклад) Откат вандализма |
Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Искусственное дыхание''' — комплекс мер, направленных на поддержание оборота воздуха через легкие у человека (или животного), переставшего дышать. Может производиться с помощью аппарата искусственного дыхания, либо человеком (дыхание изо рта в рот). Обычно совмещается с [[искусственный массаж сердца|искусственным массажем сердца]]. Типичные ситуации, в которых требуется искусственное дыхание: несчастные случаи в результате автомобильных аварий, происшествия на воде, поражение электрическим током, утопление. Аппарат искусственного дыхания используется также в хирургических операциях. |
|||
Палиндром — строка, читающаяся одинаково как слева направо, так и справа налево. Например строка abba является палиндромом. |
|||
Задача найти все количество подстрок строки которые являются палиндромами. |
|||
=== Искусственное дыхание «рот-в-рот» === |
|||
== Алгоритмы поиска количества подпалиндромов в строке == |
|||
[[Изображение:ArificialBreath.JPG|thumb|260 px|right|Искусственное дыхание «рот-в-рот»]] |
|||
Наиболее эффективный способ искусственного дыхания. |
|||
# Спасите пострадавшего, уберите от него ток, если он им поражён, вытащите из воды при утоплении, обеспечьте его безопасность. |
|||
# Положите пострадавшего на спину. Откройте ему рот, следите, чтобы язык не закрывал гортань. |
|||
# Одной рукой удерживайте голову и шею пострадавшего, другой зажмите его нос. Глубоко вдохните и, плотно прижавшись ртом ко рту, сделайте выдох. |
|||
# Первые 5—10 выдохов делайте быстро (за 20—30 с), следующие— со скоростью 12—15 выдохов в минуту. |
|||
# Следите за движением грудной клетки пострадавшего: если после вашего выдоха в рот его грудная клетка поднялась, значит, дыхательные пути проходимы и искусственное дыхание вы делаете правильно. |
|||
# Если нет пульса, параллельно с искусственным дыханием необходимо делать массаж сердца. |
|||
=== Искусственное дыхание «рот-в-нос» === |
|||
=== Лобовое решение === |
|||
Проводится, если рот спасаемого повреждён или по каким-либо причинам нельзя использовать метод «рот-в-рот». Не так эффективно, как искусственное дыхание «рот-в-рот», «рот-в-нос» также способно спасти человека. |
|||
Задачу возможно решить «в лоб» для небольших строк, перебирая каждый символ и пытаясь строить от него максимальный палиндром, если этот символ является центром палиндрома (для нечетной длины) или одним из центральных символов (для палиндромов четной длины). |
|||
== См. также == |
|||
=== Решение при помощи суффиксных деревьев === |
|||
* [[Реанимация]] |
|||
Задача решается при помощи суффиксных деревьев и быстрого алгоритма LCA. Сложность такого алгоритма <math>O(N \log{N})</math>, где <math>N</math> — длина строки. |
|||
* [[Искусственный массаж сердца]] |
|||
| ⚫ | |||
=== Решение с динамическим программированием === |
|||
[[Категория:Медицина]] |
|||
Решение при помощи динамического программирования — один из самых быстрых и простых алгоритмов для решения данной задачи. |
|||
[[Категория:Первая помощь]] |
|||
Заведем массив, размер которого равен длине строки. Назовем массив <code>А</code>, и будем хранить в <code>A[i]</code> количество палиндромов с центром в символе <code>i</code>. Тогда ответом на поставленную задачу будет сумма всех элементов массива. |
|||
[[Категория:Искусственное дыхание]] |
|||
Разберем нахождение палиндрома нечетной длины от символа в строке с номером <code>i</code>. Будем сравнивать символы, отстоящие слева и справа от <code>i</code> на какое-то число <code>k</code>, и увеличивать <code>k</code> пока они равны и пока выполняются условия <code>i+k <= length(s)</code>, <code>i-k >= 1</code>. |
|||
Будем хранить границы самого правого уже найденного палиндрома. Пусть <code>L</code> — левый символ этого палиндрома, а <code>R</code> — правый. |
|||
Итак, рассматривая очередное <code>i</code>, мы проверяем, является ли оно больше правой границы самого правого из уже найденных палиндромов. Если <code>i > R</code>, то находим палиндром с центром в <code>i</code> по вышеописанному алгоритму. Если <code>i <= R</code>, то найдем элемент, симметричный <code>i</code> относительно центра самого правого палиндрома. Назовем этот элемент <code>j</code>, <code>j = R + L — i</code>. Поиск количества палиндромов для подстроки с центром в <code>i</code> можно начинать с того количества, которое записано в <code>А[j]</code>, увеличивая далее это значение по алгоритму, описанному выше. Если правая граница полученного палиндрома больше <code>R</code>, тогда обновляем <code>L</code> и <code>R.</code> |
|||
== Примеры реализации на языках программирования == |
|||
=== Pascal === |
|||
<source lang="pascal"> |
|||
r := -1; {обнуляем начальные значения l и r} |
|||
{в конце и начале строки добавляем по символу, который в строке встречаться не может} |
|||
for i:=2 to n do begin |
|||
if i>r then |
|||
x:=1 |
|||
else x:=min(a[l+r-i],r-i)+1; |
|||
while (i+x<=n)and(stroka[i-x]=stroka[i+x])and(i-x>=2) do {наращиваем x пока палиндром} |
|||
inc(x); |
|||
a[i]:=x-1; |
|||
if i+x-1>r then |
|||
begin R:=i+x-1;L:=i-x+1; end; |
|||
end;{так мы нашли количество палиндромов нечетной длины} |
|||
{четной длины находятся аналогично. все вхождения х заменить на х - 1} |
|||
</source> |
|||
| ⚫ | |||
Версия от 08:25, 8 ноября 2009
Искусственное дыхание — комплекс мер, направленных на поддержание оборота воздуха через легкие у человека (или животного), переставшего дышать. Может производиться с помощью аппарата искусственного дыхания, либо человеком (дыхание изо рта в рот). Обычно совмещается с искусственным массажем сердца. Типичные ситуации, в которых требуется искусственное дыхание: несчастные случаи в результате автомобильных аварий, происшествия на воде, поражение электрическим током, утопление. Аппарат искусственного дыхания используется также в хирургических операциях.
Искусственное дыхание «рот-в-рот»
Наиболее эффективный способ искусственного дыхания.
- Спасите пострадавшего, уберите от него ток, если он им поражён, вытащите из воды при утоплении, обеспечьте его безопасность.
- Положите пострадавшего на спину. Откройте ему рот, следите, чтобы язык не закрывал гортань.
- Одной рукой удерживайте голову и шею пострадавшего, другой зажмите его нос. Глубоко вдохните и, плотно прижавшись ртом ко рту, сделайте выдох.
- Первые 5—10 выдохов делайте быстро (за 20—30 с), следующие— со скоростью 12—15 выдохов в минуту.
- Следите за движением грудной клетки пострадавшего: если после вашего выдоха в рот его грудная клетка поднялась, значит, дыхательные пути проходимы и искусственное дыхание вы делаете правильно.
- Если нет пульса, параллельно с искусственным дыханием необходимо делать массаж сердца.
Искусственное дыхание «рот-в-нос»
Проводится, если рот спасаемого повреждён или по каким-либо причинам нельзя использовать метод «рот-в-рот». Не так эффективно, как искусственное дыхание «рот-в-рот», «рот-в-нос» также способно спасти человека.