Хеш-функція Далла#4905

Хеш-функція Далла

1 секунда

64 мегабайти

Середня

Професор Далл дуже любить вигадувати нові "гарні" хеш-функції для рядків. Нещодавно він опублікував статтю з описом наступного методу. Даний метод використовує два параметри: улюблений рядок $W$ та натуральне число $K$ , що не перевищує довжину $W$ . Хеш-функція застосовується до рядка $S$ . Спочатку у рядку $S$ знаходять усі його підрядки, які є анаграмами рядка $W$ . З цих анаграм обирають лексикографічно найбільший підрядок $A_{1}$ A_1 та найменший $A_{2}$ A_2. Далі для кожної пари підрядків довжини $K$ з $A_{1}$ A_1 та $A_{2}$ A_2 підраховують кількість однакових символів на однакових позиціях. Сума цих значень і є шуканим значенням хеш-функції. Якщо у $S$ немає підрядків, які є анаграмами $W$ , значення хеш-функції дорівнює $0$ .

Підрядком називається будь-яка послідовність символів заданого рядка, що йдуть підряд. Анаграма — рядок, отриманий перестановкою букв іншого рядка.

Вхідні дані

У першому рядку введено натуральне число $K$ . У другому рядку записано рядок $W$ , довжина якого — натуральне число, що не перевищує $3000$ . Число $K$ не перевищує довжину рядка $W$ . У третьому рядку міститься рядок $S$ , довжина якого не перевищує $100000$ . Гарантується, що кількість позицій рядка $S$ , у яких починаються підрядки, що є анаграмами $W$ , не перевищує $2000$ . Усі рядки складаються лише з малих латинських літер.

Вихідні дані

Виведіть обчислене значення хеш-функції Далла.

Пояснення до прикладу 1: Підрядки-анаграми: $bab$ , $abb$ , $bba$ (у порядку появи). Найбільший — $bba$ , найменший — $abb$ . У кожному рядку по $2$ підрядки довжини $K = 2$ K = 2. Кількість збігів у $bb$ та $ab$ — $1$ , у $bb$ та $bb$ — $2$ , у $ba$ та $ab$ — $0$ , у $ba$ та $bb$ — $1$ . Всього $4$ збіги.

Приклади

Приклад 1