string
You are given strings S and P. Your task is to find the number of occurrences of string P inside S under the condition that the order of elements of P is not important.
For example, let S be "ACDDCD" and P be "DCD". The solution is 3 since we can find P inside S three times: as "CDD" on position 2, as "DDC" on position 3 and as "DCD" on position 4.
InputThe first two lines of input contain two integers N and M (1 \leq N, M \leq 200 000), the lengths of string S and string P, respectively.
Next two lines contain strings S and P, respectively.
Both strings consist only of upper-case letters of English alphabet.
Next two lines contain strings S and P, respectively.
Both strings consist only of upper-case letters of English alphabet.
OutputWrite a single integer that represents the number of occurrences of P inside S as explained above.
Input
Output
7
3
JSDNSJDE
DSJOutput
2Input
Output
6
2
ABABAB
ABOutput
5Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.