题目描述
Given two strings $T_1$ and $T_2$, a string $X$ is $T$-nested if and only if $X$ can be represented as the string obtained by inserting $T_2$ at a position in $T_1$. For example, if $T_1=\texttt{abcd}$ and $T_2=\texttt{ef}$, then $\texttt{efabcd}$, $\texttt{aefbcd}$ and $\texttt{abcdef}$ are all $T$-nested strings.
Given strings $S$, $T_1$, and $T_2$, your task is to compute the count of distinct $T$-nested substrings in $S$. Two nested substrings are considered distinct if they either occur at different positions in $S$, or [b]the insert positions of $T_2$ in $T_1$ are different[/b]. A substring of $S$ means a continuous sequence of characters from string $S$.
Given strings $S$, $T_1$, and $T_2$, your task is to compute the count of distinct $T$-nested substrings in $S$. Two nested substrings are considered distinct if they either occur at different positions in $S$, or [b]the insert positions of $T_2$ in $T_1$ are different[/b]. A substring of $S$ means a continuous sequence of characters from string $S$.
输入
Ensure to use cin/cout and disable synchronization with stdio to avoid unexpected TLE verdict.
The first line contains a single integer $T$ ($1\le T\le 20$), denoting the number of test cases.
The first line of each test case contains two strings $T_1$ and $T_2$ ($|T_1|+|T_2|\le |S|$) separated by a single space.
The second line of each test case contains a single string $S$ ($|S|\le 10^7$).
It is guaranteed that $S$, $T_1$, and $T_2$ all consist only of lowercase letters and $\sum |S|\le 2\times 10^7$. Here, $|S|$ means the length of string $S$.
The first line contains a single integer $T$ ($1\le T\le 20$), denoting the number of test cases.
The first line of each test case contains two strings $T_1$ and $T_2$ ($|T_1|+|T_2|\le |S|$) separated by a single space.
The second line of each test case contains a single string $S$ ($|S|\le 10^7$).
It is guaranteed that $S$, $T_1$, and $T_2$ all consist only of lowercase letters and $\sum |S|\le 2\times 10^7$. Here, $|S|$ means the length of string $S$.
输出
For each test case, output an integer in a single line representing the number of distinct $T$-nested substrings in $S$.
样例输入 Copy
3
abab ab
abababab
ab a
aaabbaabaa
aba ab
ababaabbabaab
样例输出 Copy
6
5
5
提示
In the first test case, the $6$ $T$-nested substrings are (the substring is underlined and the part from $T_2$ is highlighted in bold):
- $\underline{\textbf{ab}\text{abab}}\text{ab}$
- $\underline{\text{ab}\textbf{ab}\text{ab}}\text{ab}$
- $\underline{\text{abab}\textbf{ab}}\text{ab}$
- $\text{ab}\underline{\textbf{ab}\text{abab}}$
- $\text{ab}\underline{\text{ab}\textbf{ab}\text{ab}}$
- $\text{ab}\underline{\text{abab}\textbf{ab}}$