Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: writing.in

Rezultatų failas: writing.out

Jei norite pateikti savo sprendimą - prisijunkite.

Majų rašmenų dešifravimas

Majų rašmenų dešifravimas pasirodė sunkesnis nei manyta. Maždaug po dviejų šimtų metų tyrinėjimų, nedaug kas buvo suprasta. Ir tik per pastaruosius tris dešimtmečius padaryta pažanga.

Majų rašmenys paremti mažais piešiniais, vadinamaisiais glifais, kurie vaizduoja garsus. Majų kalbos žodžiai buvo rašomi glifų, nupieštų įvairiose pozicijose, rinkiniais.

Viena problemų, kuri iškyla dešifruojant majų raštą, yra glifų skaitymo tvarka. Piešdami glifus (tam, kad iš jų sudarytų žodį) majai kartais konkretaus glifo poziciją parinkdavo ne remdamiesi kokia nors tvarka, o savo estetiniu jausmu. Tai reiškia, kad nors ir žinoma, kokį garsą atitinka koks glifas, archeologai nėra tikri, kaip reikėtų ištarti užrašytą žodį.

Archeologai tiria tam tikrą žodį W. Jie žino šio žodžio glifus, tačiau nežino, kokia tvarka žodyje išdėlioti glifai. Jie paprašė jūsų pagalbos. Archeologai pateiks žodį W sudarančius glifus – jų skaičius lygus g – ir visus S glifų, esančių tiriamame rašte (glifai pateikti ta tvarka, kuria jie sutinkami rašte). Raskite, kiek kartų žodis W sutinkamas sekoje S, t. y. kiek kartų sekoje S sutinkamos nuosekliai einančių visų žodį W sudarančių glifų sekos, t.y. permutacijos.

Pradiniai duomenys

Pirmoje eilutėje įrašyti du tarpu atskirti sveikieji skaičiai g ir |S| (1\\leg\\le3~000; g\\le|S|\\le3~000~000). Antroje eilutėje įrašyta g simbolių be tarpų, reiškiančių glifus žodyje W. Trečioje eilutėje įrašyta |S| simbolių be tarpų, reiškiančių glifus majų rašte. Glifai išreikšti simboliais a-z ir A-Z; didžiosios ir mažosios raidės laikomos skirtingomis.

Rezultatai

Vienintelėje eilutėje reikia įrašyti, kiek kartų žodis W sutinkamas glifų sekoje S.

Pavyzdys

Duomenys Rezultatai
4 11
cAda
AbrAcadAbRa
2