Алгоритми для пошуку палиндромов

image

Сьогодні я хочу вам розповісти про алгоритм підрахунку кількості палиндромов в рядку: для чого це потрібно, де застосовується, як це швидко зробити, які підводні камені нас очікують і багато іншого. Розглянемо різні способи для вирішення даної задачі, з'ясуємо плюси і мінуси кожного способу. Ця стаття буде оглядової: якщо я щось не описую тут, то постараюся завжди дати вам набір посилань, де все детально описано і розписано. Сподіваюся, що матеріал буде цікавий як новачкам у сфері алгоритмів, так і досвідченим програмістам. Що ж, якщо я зміг зацікавити вас, то прошу під кат!

Для початку варто згадати, що ж таке паліндром.

Паліндром — число (наприклад, 404), буквосполучення, слово або текст, однаково читающееся в обох напрямках. Іноді паліндромом називають будь-симетричний щодо своєї середини набір символів.(витяг з Википедии)

Визначення дуже легке і зрозуміле. Ми в даному пості будемо розглядати паліндроми-слова(поп, кок і т. д.). Але це не означає, що алгоритми застосовують для інших ситуацій. Просто трохи звузити область.

Для чого може знадобитися шукати паліндроми?

Насправді, не дуже то й часто доводиться шукати паліндроми в повсякденному житті. Аж надто специфічна це завдання. Якщо говорити про строкових алгоритмах, то ми набагато частіше зустрічаємо той самий пошук підрядка в рядку, ніж знаходження кількості палиндромов. Тому і висвітлення в літературі набагато слабкіше.

Одне з основних застосувань — спортивне/олімпіадний програмування. Там задач на таке вистачає. Завдань понаписують, а учасникам вже думай, яким способом це вирішити. З особистого досвіду скажу, що мені такі завдання зустрічалися всього кілька разів, але всі вони були з розряду «ось тобі завдання, ти не думай, а просто напиши алгоритм». Тобто не цікаві завдання, які розвивають просто механічну пам'ять з набивання алгоритмів.

А більш практичне застосування знаходження палиндромов — це біологічні алгоритми. Згідно все тієї ж Вікіпедії і посиланнях знизу Вікі, палиндромность біологічних сполук відіграє важливу роль на властивості різних біологічних сполук. Я в біології слабкий, тому якщо вам цікаво, то ви можете знайти більш детальну інформацію самі.

Відмінно, ми з'ясували, що ми будемо займатися не зовсім непотрібними справами. Давайте вже перейдемо до розгляду алгоритмів!

Зауваження: у всіх наведених нижче алгоритмах одиночний символ не вважається за паліндром. Як ви розумієте, це легко виправити, якщо одиночні символи теж потрібно буде врахувати.

0) Самий банальний алгоритм з асимптотикой O(N^3)

bool SlowN3::isPalindrom(int leftBorder, int rightBorder)
{
while(leftBorder <= rightBorder)
{
if(str[leftBorder] != str[rightBorder])
{
return false;
}
++leftBorder;
--rightBorder;
}
return true;
}

long long SlowN3::operator ()()
{
for(int leftBorder = 0;leftBorder < str.length(); ++leftBorder)
{
for(int rightBorder = leftBorder + 1; rightBorder < str.length(); ++rightBorder)
{
if( isPalindrom(leftBorder, rightBorder) )
{
++cntPalindromes;
}
}
}
return cntPalindromes;
}

Хочу відразу попередити, що всі вихідні коди будуть на C++, і це будуть значущі частини класів, які нам можуть бути цікаві.

Алгоритм самий що ні на є «лоб»: є рядок, є вказівник на початок підрядка даної рядки, є вказівник на кінець даної підрядка. В двох вкладених циклах перебираємо кордону підрядків і банально перевіряємо, чи є наша підрядок паліндромом. Нічого складного.

Але це все жахливо повільно працює. Чому? Та тому що ми квадрат від N раз (N у нас буде завжди довжина рядка) перебираємо кордону тче підрядка, а потім ще й за O(N) у гіршому випадку виконуємо перевірку для кожної підрядка на палиндромность.

Плюсів у цього способу небагато:

+ Легко реалізується. Дійсно, залишити багу тут ну дуже складно.
+ Легко читається. Ви тільки глянули, і вже зрозуміли, що так як тут працює.
+ Мала прихована константа. Як відомо, на час роботи алгоритму впливає не тільки асимптотична оцінка (тут ми працюємо тільки з гіршими випадками), але і прихована константа. У цього алгоритму прихована константа вкрай мала.

Мінуси:

— Дуже мала швидкість роботи. Як ви можете бачити, що при рядку з тисячі літер 'a' даний алгоритм зробить порядку 10^9 ітерацій, що є дуже погано. А що якщо рядок довжиною 100000?

1) Самий банальний алгоритм з асимптотикой O(N^2)

Код:

void SlowN2::oddCount()
{
for(int indMiddle = 0; indMiddle < str.length(); ++indMiddle)
{
int leftBorder = indMiddle - 1, rightBorder = indMiddle + 1;
while(leftBorder >= 0 && rightBorder < str.length() && str[leftBorder] == str[rightBorder])
{
++cntPalindromes;
--leftBorder;
++rightBorder;
}
}
}

void SlowN2::evenCount()
{
for(int indMiddle = 0; indMiddle < str.length(); ++indMiddle)
{
int leftBorder = indMiddle, rightBorder = indMiddle + 1;
while(leftBorder >= 0 && rightBorder < str.length() && str[leftBorder] == str[rightBorder])
{
++cntPalindromes;
--leftBorder;
++rightBorder;
}
}
}

Тут вже трохи цікавіше. У нас є рядок, і два тимчасових масиву для палиндромов парної і непарної довжини. А число у клітинці i масиву буде зберігати кількість палиндромов в рядку s(вихідна рядок) з центром в точці i. Для непарної довжини палиндрома центр знаходиться легко, ну а для парної ми просто трохи пограємося з індексами і змістимо трішки центр(що видно в коді). Наш результат-це є сума чисел з двох масивів.

Як бачите, знову нічого складного. Але це працює помітно швидше попереднього алгоритму. Чому? Давайте розглянемо, як же воно все працює.

Ми біжимо по рядку, перебираючи центральний символ нашого потенційного палиндрома. А потім просто біжимо вліво і вправо від центрального елемента до тих пір, поки символи однакові. Як тільки вони стали різними, це означає, що далі не буде палиндромов з центром у нашому вибраному елементі, і переходимо до наступного.

А працює це швидко на звичайних рядках дуже швидко тому, що наш другий, вкладений цикл, який біжить до тих пір, поки крайні символи рівні, обривається вкрай швидко(якщо припустити, що палиндромов в рядку багато менше загального числа підрядків).

Розглянемо плюси і мінуси способу.

Плюси:

+ Усі також легко кодится. Помилитися дуже складно.
+ Мала прихована константа
+ Добре веде себе на випадкових рядках

Мінуси:

— Ще довгий час роботи

Після цього способу вже голова починає думати-думати-думати. І тут ідея! А що якщо ми модифікуємо цей спосіб, тільки будемо від центрального елемента стрибати не на 1 символ з кожною ітерацією, а трішки більше? І тут нам на допомогу приходять…

2) Використовуємо хеші!

Цей спосіб трохи складніше, тому відразу наведу код, а потім постараюся пояснити, що за магія там твориться(хоча магії немає, як ви самі прекрасно знаєте):

inline long long Hash::getHash(int indLeft, int indRight) const
{
return prefixHash[indRight] - (indLeft > 0 ? prefixHash[indLeft - 1] : 0);
}

inline long long Hash::getRevHash(int indLeft, int indRight) const
{
return suffixHash[indLeft] - (indRight < suffixHash.size() - 1 ? suffixHash[indRight + 1] : 0);
}

void Hash::PrepareSimpleNumbers()
{
if(str.length() > simpleNumbers.size())
{
size_t oldSize = simpleNumbers.size();
simpleNumbers.resize(str.length());
simpleNumbers[0] = 1LL;
for(int i = oldSize; i < simpleNumbers.size(); ++i)
simpleNumbers[i] = simpleNumbers[i - 1] * SimpleBase;
}
}

void Hash::CountingPrefixHash()
{
prefixHash[0] = str[0];
for(int i = 1; i < prefixHash.size(); ++i)
{
prefixHash[i] = prefixHash[i - 1] + str[i] * simpleNumbers[i];
}
}

void Hash::CountingSuffixHash()
{
suffixHash[suffixHash.size() - 1] = str[str.length() - 1];
for(int i = (int) str.length() - 2, j = 1; i >= 0; --i, j++)
{
suffixHash[i] = suffixHash[i + 1] + str[i] * simpleNumbers[j];
}
}

bool Hash::isPalindrome(int indLeft, int indRight) const
{
return getHash(indLeft, indRight) * simpleNumbers[prefixHash.size() - indRight - 1] ==
getRevHash(indLeft, indRight) * simpleNumbers[indLeft];
}

void Hash::CountingOdd()
{
for (int i = 0; i < oddCount.size(); i++)
{
int indLeft = 1, indRight = min(i + 1, static_cast<int> (oddCount.size() - i));
while (indLeft <= indRight)
{
int middle = (indLeft + indRight) / 2;
if (isPalindrome(i - middle + 1, i + middle - 1))
{
oddCount[i] = middle - 1;
indLeft = middle + 1;
}
else
{
indRight = middle - 1;
}
}
}
}

void Hash::CountingEven()
{
for (int i = 0; i < evenCount.size(); i++)
{
int indLeft = 1, indRight = min(i, static_cast<int> (evenCount.size() - i));
while (indLeft <= indRight)
{
int middle = (indLeft + indRight) / 2;
if (isPalindrome(i - middle, i + middle - 1))
{
evenCount[i] = middle;
indLeft = middle + 1;
}
else
{
indRight = middle - 1;
}
}
}
}

long long Hash::operator()()
{
PrepareSimpleNumbers();
CountingPrefixHash();
CountingSuffixHash();
CountingOdd();
CountingEven();
for(int i = 0; i < str.length(); ++i)
{
cntPalindromes += oddCount[i] + evenCount[i];
}
return cntPalindromes;
}

Коротка суть даного способу: ми перебираємо центральний елемент нашого палиндрома, і потім дихотомією намагаємося знайти найбільший радіус нашого палиндрома (під радіусом тут розуміється відстань від центрального елемента до крайнього, якщо у нас паліндром парної довжини, то просто додамо трішки гри з індексами, щоб все працювало). Під час підбору ми повинні якось швидко порівнювати підрядка на ідентичність. робимо це за допомогою хешів. Асимптотика, як легко здогадатися: N витрачаємо на перебір центрального елемента, logN в гіршому випадку витрачаємо на підбір радіусу палиндрома, за одиницю порівнюємо підрядки з допомогою хешів. Разом маємо O(NlogN), що дуже навіть непогано насправді.

Тепер трохи докладніше зупинимося на цьому методі.

На чому ґрунтується наш метод? Так як ми перебираємо центральний елемент, а потім дихотомією підбираємо радіус найбільшого палиндрома з центром в даному елементі, то ми повинні швидко брати хеш лівій частині нашого потенційного палиндрома і порівнювати його з хешем правій частині нашого потенційного палиндрома.

Як це зробити? Давайте попередньо розрахуємо хеш для кожного префікса та суфікса вихідної рядки. У коді це у нас роблять методи CountingPrefixHash() і CountingSuffixHash() відповідно.

За допомогою методів getHash() і getRevHash() ми можемо швидко отримати хеш лівої і правої частин розглядуваного на даному етапі потенційного палиндрома. Тут може виникнути питання, чому не можна скористатися однією і тією ж функцією підрахунку хеш для лівої і правої частин. А все тому, що ми при перевірці на палиндромность ліву частину ми читаємо зліва направо, а другу справа наліво. І нам необхідно підтримувати хеш зліва направо і справа наліво.

Залишилася єдина складність: як порівняти ці 2 хеш? І цю проблему ми вирішуємо за допомогою методу isPalindrome(), який призводить хеші до одного основи і порівнює їх.

Результатом кожної ітерації у нас буде кількість палиндромов з центром i. Пробегаемся 2 рази для палиндромов парної і непарної довжини, відповідь на наше завдання є сума всіх значень масивів oddCount і evenCount

Більш докладно про цей метод ви можете почитати в цієї статті.

Плюси:

+ Асимптотично ми знизили до NlogN, що не може не радувати. Якщо брати тільки найгірші випадки, то в теорії коли-небудь ми виграємо

Мінуси:

— Досить важко пишеться. Легко посіяти багу. Потрібна трохи теоретична підготовка в області хешів.
— Повільно працює на випадкових тестах. Ви можете самі в цьому переконатися. А все із-за великої прихованої константи і з-за того, що навіть якщо у нас немає жодного палиндрома з центром в даному елементі, то алгоритм зробить logN стрибків, а це все займає час.
— Колізії. Як ви бачите, в моєму исходнике використовується хеш, який зазвичай пишуть на олімпіадах з програмування(так-так, я трохи цим колись займався). Так от, на змаганнях даний спосіб показує себе добре. Особисто у мене колізії не траплялися. Але я знаю про способи спокійно даний хеш завалити(зокрема з використанням рядків Туэ-Морсу). Я колись чув, що є якийсь фиббоначиевый хеш, який начебто не ламається на даному тесті, але інформація недостовірна. Так що будьте обережні з колізіями.

А якщо ми хочемо 100% рішення без всякої там коллизийной поправки і введення хешу за іншою підставою і так далі?

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

Код:

//Find palindroms like 2*N+1
void Manacker::PalN2()
{
int leftBorder = 0, rightBorder = -1, tempMirror;//start digits for algortihm
for(int i = 0; i < str.length(); ++i)
{
tempMirror = (i > rightBorder ? 0 : std::min(ansPalN2[leftBorder + rightBorder - i], 
rightBorder - i)) + 1;//find mirror of current index
while(i + tempMirror < str.length() && i - tempMirror >= 0 && 
str[i - tempMirror] == str[i + tempMirror])//increase our index
{
++tempMirror;
}
ansPalN2[i] = --tempMirror;
if(i + tempMirror > rightBorder)//try to increase our right border of palindrom
{
leftBorder = i - tempMirror;
rightBorder = i + tempMirror;
}
}
}

void Manacker::Pal2()
{
int leftBorder = 0, rightBorder = -1, tempMirror;
for(int i = 0; i < str.length(); ++i)
{
tempMirror = (i > rightBorder ? 0 : std::min(ansPal2[leftBorder + rightBorder - i + 1],
rightBorder - i + 1)) + 1;
while(i + tempMirror - 1 < str.length() && 
i - tempMirror >= 0 && str[i - tempMirror] == str[i + tempMirror - 1])
{
++tempMirror;
}
ansPal2[i] = --tempMirror;
if(i + tempMirror - 1 > rightBorder)
{
leftBorder = i - tempMirror;
rightBorder = i + tempMirror - 1;
}
}
}

Отже, ми отримали з допомогою хешів алгоритм за NlogN. Але хочеться швидше. Хочеться чогось лінійного. І тут нам на допомогу поспішає Алгоритм Манакера (за посиланням ви також можете бачити реалізацію алгоритму на Java), який мало того, що линеен, так ще й має вкрай малою прихованої константою, що позитивно позначається на швидкості роботи. Детально описувати спосіб я не буду, так як це вийде переказ цієї чудової посилання (я сам навчав алгоритм саме за цим посиланням). Тут я наведу злегка пересказанное пояснення.

Алгоритм полягає в тому, що ми обробляємо рядок символ за символом, підтримуючи правий паліндром в нашій рядку. І на кожній ітерації дивимося, наш поточний елемент знаходиться всередині кордонів самого правого палиндрома чи ні. Якщо знаходиться, то ми можемо отримати відповідь з раніше порахованих значень, шляхом нехитрих маніпуляцій з індексами. Якщо ж не знаходиться, то ми йдемо точно таким же алгоритмом, який описаний в пункті 1) цього огляду: йдемо символ за символом і порівнюємо дзеркальні елементи відносно центру. Йдемо до тих пір, поки вони рівні. І не забуваємо оновити після цього кордону самого правого знайденого палиндрома. Це коротко. Про деякі підводні камені ви можете почитати в наведеній статті.

Що ще цікавого: у всіх завданнях, які я вирішував на контестах (за олімпіадного програмування), вистачало саме цього алгоритму. Дуже просто пишеться, якщо ти його писав N раз вдома і вже знаєш напам'ять.

Плюси:

+ Досить короткий код.
+ Дуже швидко працює. Мало того, що асимптотика O(N), так ще й мала прихована константа.

Мінуси:

— Ідея не така проста, щоб самому сходу придумати даний алгоритм
— Можна заплутатися у всяких індексах, якщо проявити неуважність при написанні коду

А чи є інші способи вирішити дану задачу за лінійний час?

4) Дерево палиндромов

Трохи передісторії. Цю відносно нову структуру даних відкрив Михайло Рубінчик rumi13 і представив її на Петрозаводских зборах. Структура вкрай цікава своєю з одного боку простотою, а з іншого тим, що дозволяє швидко вирішувати досить широкий спектр задачі про паліндроми. І найголовніше — дозволяє досить просто рахувати кількість палиндромов у рядку за O(N) (але саме дерево палиндромов думаю придумувалося далеко не для цього, а для більш серйозних завдань з паліндромами).

Код:

PalindromicTree::PalindromicTree(const std::string& s) : FindPalindrome(s)
{
initTree();
}

PalindromicTree::~PalindromicTree()
{
for(int i = 0;i < pullWorkNodes.size(); ++i)
{
delete pullWorkNodes[i];
}
}

void PalindromicTree::initTree()
{
root1 = new Node;
root1->len = -1;
root1->sufflink = root1;
root2 = new Node;
root2->len = 0;
root2->sufflink = root1;
suff = root2;
pullWorkNodes.push_back(root1);
pullWorkNodes.push_back(root2);
}

void PalindromicTree::findAddSuffix(Node* &cur, int pos, int& curlen)
{
while (true)
{
curlen = cur->len;
if (pos - 1 - curlen >= 0 && str[pos - 1 - curlen] == str[pos])
{
break;
}
cur = cur->sufflink;
}
}

void PalindromicTree::makeSuffixLink(Node* &cur, int pos, int& curlen,int let)
{
while (true)
{
cur = cur->sufflink;
curlen = cur->len;
if (pos - 1 - curlen >= 0 && str[pos - 1 - curlen] == str[pos])
{
suff->sufflink = cur- > next[let];
break;
}
}
}

void PalindromicTree::addLetter(int pos)
{
Node* cur = suff;
int let = str[pos] - 'a', curlen = 0;
findAddSuffix(cur, pos, curlen);
if (cur- > next[let] != nullptr)
{
suff = cur- > next[let];
return;
}
suff = new Node;
pullWorkNodes.push_back(suff);
suff->len = cur->len + 2;
cur- > next[let] = suff;
if (suff->len == 1)
{
suff->sufflink = root2;
suff->num = 1;
return;
}
makeSuffixLink(cur, pos, curlen, let);
suff->num = 1 + suff->sufflink->num;
}

long long PalindromicTree::operator ()()
{
for (int i = 0; i < str.length(); ++i)
{
addLetter(i);
cntPalindromes += suff->num - 1;
}
return cntPalindromes;
}

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

Отже, ідея дерева. У вершинах нашого дерева будуть знаходитися тільки самі паліндроми: 'a', 'b', 'aba' і так далі. Зрозуміло, що сам паліндроми ми не будемо зберігати, а просто будемо зберігати з якої вершини ми прийшли сюди, і який символ з двох сторін додали. Також у нас існують дві фіктивні вершини для зручної реалізації алгоритму.

Але як і в будь-якому цікавому дереві, у нас також існують суффиксные посилання. Суффиксная посилання буде вести на вершину, яка також є паліндромом (ну тому що у нас в вершинах зберігаються тільки паліндроми) і яка є найбільшим власним суфіксом даної вершини. Тобто з вершини 'aba' посилання буде вести на вершину 'a'.

Далі, ми по черзі додаємо символи в дерево по одному. І завдяки хитрому пристрою дерева і рекурсивну операції додавання (а також суффиксным посиланнями, за якими здійснюється перехід), ми оновлюємо все дерево.

Це коротко, детальніше почитайте інформацію по посиланню вище (якщо не боїтеся англійської)

Плюси:

+ Якщо Ви раніше працювали з деревами, то вам буде дуже просто зрозуміти дану ідею.
+ Дозволяє вирішувати великий спектр завдань на паліндроми

Мінуси:

— Працює повільніше, ніж алгоритм Манакера.
— Можна поставити багу. Але, чисто суб'єктивно, тут це зробити складніше, ніж в тому ж алгоритмі Манакера.

Також варто згадати, що з допомогою дерев існує ще одне рішення даної задачі. Воно полягає у використанні суфіксного дерева і швидкого алгоритму LCA(який працює за препроцессинг O(N) і відповідь на запит O(1). Алгоритм Фарах-Колтон-Бендера). Але він на практиці не застосовується, так як досить складний і у нього дуже велика прихована константа. Представляє скоріше академічний інтерес.

Що може бути ще цікаво про алгоритми? Правильно, споживання пам'яті і час роботи.
На гітхабі Ви можете завантажити також код для тестування, який генерує випадкові рядки і шукає в них паліндроми.

Моє тестування показало, що очікувано алгоритм номер 0 працює вкрай повільно. Лідером, як Ви можете здогадатися, є алгоритм Манакера. Але що найцікавіше: алгоритм з O(N^2) виграє з приблизно дворазовим відривом у алгоритму з використанням хешів з O(NlogN), що ще раз доводить, що не асимптотикой єдиної міряються алгоритми. Так відбувається з-за особливостей алгоритму відсікання номер 1", і відсутність оної в способі з хешами. Що стосується дерева палиндромов, то воно програє Манакеру в основному з-за операцій з пам'яттю, так як доводиться виділяти пам'ять під кожну нову вершину. Але якщо використовувати, наприклад, new з розміщенням, то розрив скоротиться.

Пам'ять всі алгоритми споживають лінійно від розміру вхідних даних.

На цьому ми завершимо наш огляд. Сподіваюся, що ви почерпнули для себе хоч щось нове і вам було хоч трішки цікаво! Всі вихідні коди ви можете знайти в моєму публічному репозиторії на Github.

P. S. Якщо ви помітили якісь помилки, неточності або у вас є доповнення, прошу відписуватися в коментарях і писати в ЛС.
P. P. S.: Сміливо задавайте питання в коментарях — постараюся відповісти, якщо вистачить моєї компетенції.

Корисні посилання, які можуть бути вам цікаві після прочитання цієї статті (деякі посилання можуть повторюватися, так як могли проскакувати в самій статті):

0) Що таке паліндром
1) Алгоритм Манакера: Вики Codeforces, e-maxx
2) Трохи про хеші та їх застосування: e-maxx, Habrahabr
3) Обговорення про завал хешів на Codeforces: тиць
4) Рядка (слова) Туэ-Морсу: раз два
5) Статті про дерево палиндромов: гарне опис, codeforces
6) Ось ще цикл статей про пошук чисел-палиндромов: Хабр

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.