Алгоритмы нахождения палиндрома в строке.

Палиндро́м — число (например, 404), буквосочетание, слово или текст, одинаково читающееся в обоих направлениях. Иногда палиндромом называют любой симметричный относительно своей середины набор символов.(выдержка из Википедии)

Алгоритм Манакера

[править] Идея

Алгоритм, который будет описан далее, отличается от наивного тем, что использует значения, посчитанные ранее. Будем поддерживать границы самого правого из найденных палиндромов — . Итак, пусть мы хотим вычислить — т.е. длину наибольшего палиндрома с центром в позиции . При этом все предыдущие значения в массиве уже посчитаны. Возможны два случая:

1. , т.е. текущая позиция не попадает в границы самого правого из найденных палиндромов. Тогда просто запустим наивный алгоритм для позиции .

2. . Тогда попробуем воспользоваться значениями, посчитанным ранее. Отразим нашу текущую позицию внутри палиндрома . Поскольку и — симметричные позиции, то если , мы можем утверждать, что и . Это объясняется тем, что палиндром симметричен относительно своей центральной позиции. Т.е. если имеем некоторый палиндром длины с центром в позиции , то в позиции , симметричной относительно отрезка тоже может находиться палиндром длины . Это можно лучше понять, посмотрев на рисунок. Снизу фигурными скобками обозначены равные подстроки. Однако стоит не забыть про один граничный случай: что если выходит за границы самого правого палиндрома? Так как информации о том, что происходит за границами это палинлрома у нас нет (а значит мы не можем утверждать, что симметрия сохраняется), то необходимо ограничить значение следующим образом: . После этого запустим наивный алгоритм, который будет увеличивать значение , пока это возможно.

После каждого шага важно не забывать обновлять значения .

Заметим, что массив считается аналогичным образом, нужно лишь немного изменить индексы.

[править] Псевдокод

Приведем код, который вычисляет значения массива :

// — исходнаястрока

int[] calculate1(string s):

int l = 0

int r = -1

for i = 1 to n

int k = 0

if i <= r

k = min(r - i, d[r - i + l])

while i + k + 1 <= n and i - k - 1 > 0 and s[i + k + 1] == s[i - k - 1]

k++

[i] = k

if i + k > r

l = i - k

r = i + k

return

 

Битовые операции в языках программирования.

Побитовое И

Побитовое И используется для выключения битов. Любой бит, установленный в , вызывает установку соответствующего бита результата также в .

&
11001010 11100010

[править] Побитовое ИЛИ

Побитовое ИЛИ используется для включения битов. Любой бит, установленный в , вызывает установку соответствующего бита результата также в .

|
11001010 11100010

[править] Побитовое НЕ

Побитовое НЕ инвертирует состояние каждого бита исходной переменной.

~

[править] Побитовое исключающее ИЛИ

Исключающее ИЛИ устанавливает значение бита результата в , если значения в соответствующих битах исходных переменных различны.

^
11001010 11100010

[править] Побитовые сдвиги

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

Сдвиг влево может применяться для умножения числа на два, сдвиг вправо — для деления.

x = 7 // 00000111 (7)

x = x >> 1 // 00000011 (3)

x = x << 1// 00000110 (6)

x = x << 5// 11000000 (-64)

x = x >> 2 // 11110000 (-16)

В языке программирования Java существует также оператор беззнакового битового сдвига вправо . При использовании этого оператора на освободившиеся позиции всегда устанавливаются нули.

x = 7 // 00000111 (7)

x = x << 5// 11100000 (-32)

x = x >>> 2 // 00111000 (56)

 

Двоичный поиск.

int Search_Binary (int arr[], int left, int right, int key)

{

int midd = 0;

while (1)

{

midd = (left + right) / 2;

 

if (key < arr[midd]) // если искомое меньше значения в ячейке

right = midd - 1; // смещаем правую границу поиска

else if (key > arr[midd]) // если искомое больше значения в ячейке

left = midd + 1; // смещаем левую границу поиска

else // иначе (значения равны)

return midd; // функция возвращает индекс ячейки

 

if (left > right) // если границы сомкнулись

return -1;

}

}

 

int main()

{

setlocale (LC_ALL, "rus");

 

const int SIZE = 12;

int array[SIZE] = {};

int key = 0;

int index = 0; // индекс ячейки с искомым значением

 

for (int i = 0; i < SIZE; i++) // заполняем и показываем массив

{

array[i] = i + 1;

cout<< array[i] << " | ";

}

 

cout << "\n\nВведите любое число: ";

cin >> key;

 

index = Search_Binary (array, 0, SIZE, key);

 

if (index >= 0)

cout << "Указанное число находится в ячейке с индексом: " << index << "\n\n";

else

cout << "В массиве нет такого числа!\n\n";

 

return 0;

}