Степінь подібності#159

Степінь подібності (Editorial)

Степінь подібності — це кількість позицій першого рядка, для яких пара сусідніх символів s_1[i], s_1[i+1] трапляється десь у другому рядку. Зверніть увагу, що рахуються саме позиції першого рядка, а не різні пари: у прикладі з умови пара AB трапляється двічі й обидва рази йде в залік.

Звідси прямий розв'язок. Спочатку зберемо в множину (або хеш-таблицю) всі пари сусідніх символів другого рядка: це підрядки s_2[j..j+1] для від до |s_2| - 1. Потім пройдемось першим рядком і для кожної позиції перевіримо, чи є пара s_1[i..i+1] у цій множині; якщо є — збільшимо відповідь.

Оскільки алфавіт — лише великі латинські літери, замість множини рядків зручніше й швидше взяти булевий масив розміру 26 \times 26, індексований парою кодів літер. Це прибирає накладні витрати на роботу з рядками й хешуванням.

Складність — \mathcal{O}(|s_1| + |s_2|).

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