P10976 Count Repetitions

Define $str = [s, n]$ to mean that $str$ is formed by concatenating the string $s$ exactly $n$ times. For example, $str == [\texttt{abc}, 3] == \texttt{abcabcabc}$. If we can delete some characters from $s_2$ to make it become $s_1$, then we say that the string $s_1$ can be obtained from the string $s_2$. For example, by definition, $s1 = \tt{abc}$ can be obtained from $s2 = \tt{ab\red{dbe}c}$, by only deleting the characters marked in red. Now you are given two strings $s_1$ and $s_2$, and two integers $n_1$ and $n_2$. Based on them, we construct two strings: $str_1 = [s_1, n_1]$ and $str_2 = [s_2, n_2]$. Please find the maximum integer $m$ such that $str = [str_2, m]$ can be obtained from $str_1$.

This problem contains multiple test cases. There are at most $100$ test cases. For each test case, there are two lines: - The first line contains the string $s_2$ and the integer $n_2$. - The second line contains the string $s_1$ and the integer $n_1$.

For each test case, output the integer $m$ as the answer.

The testdata guarantees that $s_1$ and $s_2$ consist only of lowercase letters, and $1 \leq |s_1|, |s_2| \leq 100$, $0 \leq n_1, n_2 \leq 10^6$. For each test point, there are no more than $100$ test cases. Translated by ChatGPT 5