Dalla heş-funksiyası
Professor Dall yeni "yaxşı" sətir üçün heş-funksiyalar icad etməyi çox sevir. Yaxınlarda o, aşağıdakı metodun təsvirini dərc etdi. Sevimli sətir W alqoritmin parametrlərindən biri hesab olunur. Digər parametr isə W sətirinin uzunluğunu aşmayan bəzi təbii ədəd K-dır. Heş-funksiya S sətiri üçün hesablanır. Əvvəlcə S sətirində W sətirinin anaqramları olan bütün alt sətirlər tapılır. Bu anaqramlardan leksikoqrafik qaydada ən böyük A_1 və ən kiçik A_2 sətirləri seçilir. Daha sonra A_1 və A_2 sətirlərindən K uzunluğunda olan hər bir alt sətir cütü üçün eyni mövqedə olan eyni simvolların sayı hesablanır. Bütün bu dəyərlər toplanır - bu axtarılan dəyərdir. Əgər S sətirində W sətirinin anaqramları olan alt sətirlər yoxdursa, heş-funksiya dəyəri 0 hesab olunur.
Alt sətir verilmiş sətirin ardıcıl gedən simvollarının istənilən ardıcıllığıdır. Anaqram - verilmiş sətirin hərflərinin dəyişdirilməsi ilə əldə edilən sətirdir.
Giriş verilənləri
Giriş faylının birinci sətirində təbii ədəd K yazılıb. İkinci sətirdə W sətiri yazılıb. Onun uzunluğu 3000-i aşmayan təbii ədəddir. K sətirin W uzunluğunu aşmır. Giriş faylının üçüncü sətirində S sətiri var. Onun uzunluğu 100000-i aşmayan təbii ədəddir. S sətirində W sətirinin anaqramları olan alt sətirlərin başladığı mövqelərin sayı 2000-i aşmır. Bütün sətirlər yalnız kiçik latın hərflərindən ibarətdir.
Çıxış verilənləri
Dallın axtarılan heş-funksiya dəyərini çıxarın.
Misal 1 üçün izah: Anaqram alt sətirlər - bab, abb, bba (görünmə sırasına görə). Ən böyük - bba, ən kiçik - abb. Hər bir sətirdə cəmi K = 2 uzunluğunda 2 alt sətir var. bb və ab içindəki uyğunluqların sayı - 1, bb və bb içində - 2, ba və ab içində - 0, ba və bb içində - 1. Cəmi 4 uyğunluq.