P4595 [COCI 2011/2012 #5] POPLOČAVANJE

Note: Compared with the original problem, this version has a smaller memory limit. Some small tricks are needed to pass.

There is a street consisting of $N$ lowercase English letters. The city government occasionally replaces the tiles on the street. However, letter tiles are in high demand, so the government only has $M$ kinds of letter tiles to choose from. The pattern of the $i$-th tile consists of $L_{i}$ letters. Tiles cannot be rotated or broken, and they can only be placed where the tile’s letters exactly match a contiguous substring of letters on the street. Tiles may overlap, and multiple tiles with the same pattern may be used. If a street cannot be covered by any tiles, then it is bad. Find how many bad streets there are.

The first line contains an integer $N$, the number of letters on the street. The second line contains $N$ lowercase letters, the sequence on the street. The third line contains an integer $M$, the number of tiles. The next $M$ lines each contain $L_{i}$ lowercase letters, describing the pattern of that tile.

Print one line with an integer, the number of bad streets.

Constraints: $1\le N\le 3\times 10^{5}$, $1\le M\le 5\times 10^{3}$, $1\le L_{i}\le 5\times 10^{3}$. Translated from [COCI 2011/2012 #5 T6](https://hsin.hr/coci/archive/2011_2012/contest5_tasks.pdf). Translated by ChatGPT 5