Алгоритмы нахождения палиндрома в строке.
Палиндро́м — число (например, 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;
}