Counting Substrings

dip_BRUR Replay of Ada Lovelace Na...
Limits 1s, 512 MB

You are given a string t, a prefix p, and a suffix s. You have to find the number of distinct substrings starting with the prefix p and ending with the suffix s.

Input

There are three lines of input consisting of string t, prefix p, and suffix s. All the strings are lowercase Latin letters.

1t,p,s1051 \leq |t|, |p|, |s| \leq 10^5

Output

The only line of output is the number of distinct substrings starting with p and ending with s.

Samples

InputOutput
abcabc
a
bc
2

There are 3 substrings starting with a and ending with bc are abc, abc and abcabc. Among these abc and abcabc are distinct substring.

InputOutput
ababababa
a
b
4
InputOutput
abacbcdada
a
a
7

Submit

Login to submit.

Statistics

12% Solution Ratio
steinumEarliest, 2w ago
steinumFastest, 0.0s
steinumLightest, 14 kB
steinumShortest, 5802B
Toph uses cookies. By continuing you agree to our Cookie Policy.