Count Substring Occurrences

★★★★★

1 votes

Z algorithm, Z-algorithm, Very-Easy, Ready, Approved, String

Details

Problem

Given 2 Strings $C,S$ . Find the number of occurrences of C in S. Length of S is N, length of C is M.

Input:

Given 2 Strings $C,S$ .

Output:

Print the number of occurrences of C in S.

Constraints:

$1 \le M \le N \le 10 ^ 5$ .

Sample Input

abc
abcabdabc

Sample Output

Time Limit: 1

Memory Limit: 256

Source Limit:

Contributers: