A16191. Don't Try to Count
编程题
普及/提高-
知识点
题目描述
Given a string $x$ of length $n$ and a string $s$ of length $m$ ( $n \cdot m \le 25$ ), consisting of lowercase Latin letters, you can apply any number of operations to the string $x$ .
In one operation, you append the current value of $x$ to the end of the string $x$ . Note that the value of $x$ will change after this.
For example, if $x =$ "aba", then after applying operations, $x$ will change as follows: "aba" $\rightarrow$ "abaaba" $\rightarrow$ "abaabaabaaba".
After what minimum number of operations $s$ will appear in $x$ as a substring? A substring of a string is defined as a contiguous segment of it.
In one operation, you append the current value of $x$ to the end of the string $x$ . Note that the value of $x$ will change after this.
For example, if $x =$ "aba", then after applying operations, $x$ will change as follows: "aba" $\rightarrow$ "abaaba" $\rightarrow$ "abaabaabaaba".
After what minimum number of operations $s$ will appear in $x$ as a substring? A substring of a string is defined as a contiguous segment of it.
输入格式
The first line of the input contains a single integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases.
The first line of each test case contains two numbers $n$ and $m$ ( $1 \le n \cdot m \le 25$ ) — the lengths of strings $x$ and $s$ , respectively.
The second line of each test case contains the string $x$ of length $n$ .
The third line of each test case contains the string $s$ of length $m$ .
The first line of each test case contains two numbers $n$ and $m$ ( $1 \le n \cdot m \le 25$ ) — the lengths of strings $x$ and $s$ , respectively.
The second line of each test case contains the string $x$ of length $n$ .
The third line of each test case contains the string $s$ of length $m$ .
输出格式
For each test case, output a single number — the minimum number of operations after which $s$ will appear in $x$ as a substring. If this is not possible, output $-1$ .
输入输出样例
输入 #1
12 1 5 a aaaaa 5 5 eforc force 2 5 ab ababa 3 5 aba ababa 4 3 babb bbb 5 1 aaaaa a 4 2 aabb ba 2 8 bk kbkbkbkb 12 2 fjdgmujlcont tf 2 2 aa aa 3 5 abb babba 1 19 m mmmmmmmmmmmmmmmmmmm
输出 #1
3 1 2 -1 1 0 1 3 1 0 2 5
说明/提示
In the first test case of the example, after $2$ operations, the string will become "aaaa", and after $3$ operations, it will become "aaaaaaaa", so the answer is $3$ .
In the second test case of the example, after applying $1$ operation, the string will become " $\text{e}\color{red}{\text{force}}\text{forc}$ ", where the substring is highlighted in red.
In the fourth test case of the example, it can be shown that it is impossible to obtain the desired string as a substring.
In the second test case of the example, after applying $1$ operation, the string will become " $\text{e}\color{red}{\text{force}}\text{forc}$ ", where the substring is highlighted in red.
In the fourth test case of the example, it can be shown that it is impossible to obtain the desired string as a substring.