Количество подпалиндромов: различия между версиями

Материал из Викиучебника — открытых книг для открытого мира
Содержимое удалено Содержимое добавлено
Нет описания правки
откат
Строка 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>

[[Категория:Алгоритмы]]

Версия от 10:13, 8 ноября 2009

Палиндром — строка, читающаяся одинаково как слева направо, так и справа налево. Например строка abba является палиндромом. Задача найти все количество подстрок строки которые являются палиндромами.

Алгоритмы поиска количества подпалиндромов в строке

Лобовое решение

Задачу возможно решить «в лоб» для небольших строк, перебирая каждый символ и пытаясь строить от него максимальный палиндром, если этот символ является центром палиндрома (для нечетной длины) или одним из центральных символов (для палиндромов четной длины).

Решение при помощи суффиксных деревьев

Задача решается при помощи суффиксных деревьев и быстрого алгоритма LCA. Сложность такого алгоритма , где — длина строки.

Решение с динамическим программированием

Решение при помощи динамического программирования — один из самых быстрых и простых алгоритмов для решения данной задачи. Заведем массив, размер которого равен длине строки. Назовем массив А, и будем хранить в A[i] количество палиндромов с центром в символе i. Тогда ответом на поставленную задачу будет сумма всех элементов массива. Разберем нахождение палиндрома нечетной длины от символа в строке с номером i. Будем сравнивать символы, отстоящие слева и справа от i на какое-то число k, и увеличивать k пока они равны и пока выполняются условия i+k <= length(s), i-k >= 1. Будем хранить границы самого правого уже найденного палиндрома. Пусть L — левый символ этого палиндрома, а R — правый. Итак, рассматривая очередное i, мы проверяем, является ли оно больше правой границы самого правого из уже найденных палиндромов. Если i > R, то находим палиндром с центром в i по вышеописанному алгоритму. Если i <= R, то найдем элемент, симметричный i относительно центра самого правого палиндрома. Назовем этот элемент j, j = R + L — i. Поиск количества палиндромов для подстроки с центром в i можно начинать с того количества, которое записано в А[j], увеличивая далее это значение по алгоритму, описанному выше. Если правая граница полученного палиндрома больше R, тогда обновляем L и R.

Примеры реализации на языках программирования

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}