Counting Substrings

dip_BRUR Ada Lovelace National Gir...
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

17% Solution Ratio
steinumEarliest, 4M ago
steinumFastest, 0.0s
steinumLightest, 14 kB
RiaShirin.217029Shortest, 5801B
Toph uses cookies. By continuing you agree to our Cookie Policy.