Don't Try to Count (Codeforces 1881A)
Tags: Others, strings

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.

Input: 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$$$.

Output: 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$$$.

Note: 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.

Sample Inputs:
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

Sample Outputs:
3
1
2
-1
1
0
1
3
1
0
2
5

Solution (Python):
import sys
input = sys.stdin.readline
ini = lambda : int(input())
ins = lambda : input().strip()
inl = lambda : list(ins().split())
inli = lambda : list(map(int, inl()))

def main():
    (n, m) = inli()
    (x, s) = (ins(), ins())
    i = 0
    while True:
        if s in x:
            return i
        x += x
        i += 1
        if len(x) > len(s):
            break
    if s in x:
        return i
    x += x
    i += 1
    if s in x:
        return i
    return -1
if __name__ == '__main__':
    for _ in range(ini()):
        print(main())

Solution (Python):
import sys
import math as m
input = sys.stdin.readline

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    s = input()
    return s.strip()

def invr():
    return list(map(int, input().split()))

def doItAll(x, s):
    i = 0
    while len(x) < len(s) * 2:
        if s in x:
            return i
        x = x + x
        i += 1
    if s in x:
        return i
    if s in x + x:
        return i + 1
    return -1
numCases = inp()
for _ in range(numCases):
    (n, m) = invr()
    x = insr()
    s = insr()
    print(doItAll(x, s))

Solution (Python):
import sys
input = sys.stdin.readline

def solve():
    (n, m) = map(int, input().split())
    x = input().strip('\n')
    s = input().strip('\n')
    if x == s or s in x:
        print(0)
        return
    ans = 0
    while 1:
        ans += 1
        x = x + x
        if s in x:
            break
        if len(x) > m * n:
            break
    if len(x) > m and s not in x:
        print(-1)
    else:
        print(ans)

def main():
    t = int(input())
    for i in range(t):
        solve()
main()