String occurences 2 - MarisaOJ: Marisa Online Judge

String occurences 2

Time limit: 1000 ms
Memory limit: 256 MB
You are given 2 string $S$ and $T$. Count the number of occurrences of $T$ in $S$ (i.e. how many substrings of $S$ equal to $T$). ### Input - First line contains string $S$. - Second line contains string $C$. ### Output - The number of occurrences of $T$ in $S$. ### Constraints - $1 \le |T| \le |S| \le 10^6$. ### Example Input: ``` asasa asa ``` Output: ``` 2 ```