|
'''Искусственное дыхание''' — комплекс мер, направленных на поддержание оборота воздуха через легкие у человека (или животного), переставшего дышать. Может производиться с помощью аппарата искусственного дыхания, либо человеком (дыхание изо рта в рот). Обычно совмещается с [[искусственный массаж сердца|искусственным массажем сердца]]. Типичные ситуации, в которых требуется искусственное дыхание: несчастные случаи в результате автомобильных аварий, происшествия на воде, поражение электрическим током, утопление. Аппарат искусственного дыхания используется также в хирургических операциях.
Палиндром — строка, читающаяся одинаково как слева направо, так и справа налево. Например строка 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>
| 