POPLOCAVANJE - COCI
Mirkova ulica sastavljena je od N malih slova engleske abecede. Svakih nekoliko godina gradske vlasti obnavljaju ploče na ulici. Međutim, zbog velike potražnje slovkastih ploča, oni mogu nabaviti samo M različitih vrsta ploča.
i-ta vrsta ploče sačinjena je od Li slova. Ploča se ne smije lomiti niti okretati, a smije biti postavljena na ulicu samo na mjestima gdje se slova s ploče podudaraju s nizom uzastopnih slova na ulici.Neko polje nazivamo nepopločljivim ako ne postoji niti jedna ploča koja ga može pokriti. Izračunajte broj nepopločljivih polja.
InputPrvi redak ulaza sadrži cijeli broj N (1 ≤ N ≤ 300 000), duljinu ulice.
Drugi redak sadrži N malih slova engleske abecede, poruku zapisanu na ulici.
Treći redak sadrži cijeli broj M (1 ≤ M ≤ 5000), broj vrsta ploča.
Svaki od sljedećih redaka sadrži opis jedne vrste ploče duljine Li (1 ≤ Li ≤ 5000). Ploče će sadržavati mala slova engleske abecede.
Drugi redak sadrži N malih slova engleske abecede, poruku zapisanu na ulici.
Treći redak sadrži cijeli broj M (1 ≤ M ≤ 5000), broj vrsta ploča.
Svaki od sljedećih redaka sadrži opis jedne vrste ploče duljine Li (1 ≤ Li ≤ 5000). Ploče će sadržavati mala slova engleske abecede.
OutputU jedinom retku izlaza ispišite traženi broj nepopločljivih polja.
Input:
6
abcbab
2
cb
cbabOutput:
2Input:
4
abab
2
bac
babaOutput:
4Input:
6
abcabc
2
abca
cabOutput:
1Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.