Count Substring Occurrences

Given a string \(S\) and two integers \(L\) and \(R\) (with \(0\)-indexing), your task is to determine the number of times the substring \(S[L \ldots R]\) occurs in \(S\). In other words, let \(T = S[L:R+1]\); find the count of all indices \(i\) such that \(S[i:i+|T|] = T\).

Note: The indices are \(0\)-indexed. For example, if \(S = \texttt{ababc}\), \(L = 1\), and \(R = 3\), then the substring is \(\texttt{bab}\), which appears once in \(S\).

The mathematical formulation can be given as:

[ \text{Count} = \sum_{i=0}^{|S|-|T|} \mathbb{1}_{{S[i:i+|T|]=T}}, ]

where \(T = S[L:R+1]\) and \(\mathbb{1}\) is the indicator function.

inputFormat

The input is read from stdin and consists of two lines:

• The first line contains the string \(S\).
• The second line contains two integers \(L\) and \(R\), separated by a space.

It is guaranteed that \(0 \leq L \leq R < |S|\).

outputFormat

Output to stdout a single integer which is the number of times the substring \(S[L...R]\) occurs in \(S\).

## sample

ababc
1 3

1