https://codeforces.com/contest/1553/problem/B
시간 3초, 메모리 256MB

input :

• q (1 ≤ q ≤ 500)
• s (1 ≤ |s| ≤ 500)
• t (1 ≤ |t| ≤ 2⋅|s|−1)

output :

• For each test case, print "YES" if you can obtain the string t by performing the process mentioned in the statement with the string s, or "NO" if you cannot.
  각 테스트 케이스에서 t를 얻을 수 있다면 "YES"를 그렇지 않은 경우에는 "NO"를 출력하시오.

조건 :

• After placing the chip, you move it to the right several (maybe zero) times, i. e. you perform the following operation several times: if the current position of the chip is i, you move it to the position i+1. Of course, moving the chip to the right is impossible if it is already in the last position.
  칩을 놓은 이후에 오른쪽으로 몇 번 움직입니다. 이 행동은 아래의 조건을 따릅니다.
  현재 칩의 위치를 i라 할 때, 칩을 i + 1로 이동시킵니다. 물론 문자열의 바깥으론 이동할 수 없습니다.

• After moving the chip to the right, you move it to the left several (maybe zero) times, i. e. you perform the following operation several times: if the current position of the chip is i, you move it to the position i−1. Of course, moving the chip to the left is impossible if it is already in the first position.
  오른쪽으로 이동이 끝난 후, 칩을 왼쪽으로 몇 번 움직입니다. 이 행동은 아래의 조건을 따릅니다.
  현재 칩의 위치를 i라 할 때, 칩을 i - 1로 이동시킵니다. 물론 문자열의 바깥으론 이동할 수 없습니다.

---

처음 시간을 소요하면서 생각한 것은 오른쪽 왼쪽으로 왔다 갔다 하는 경우를 생각하는 바람에 코드를 수정해야 했다.

오른쪽 이동, 왼쪽 이동

이동하는 횟수? 라기 보다는 방향 전환이 1번만 발생해야 한다.

그렇기 target문자열을 만들 수 있는 문자라면 이 때 왼쪽으로 가도 될까? 하는 방식으로 문제를 해결했다.
결국 재귀의 방식을 사용해서 시간은 많이 소요되겠지만 사이즈가 작아서 가능 하다.

import sys
sys.setrecursionlimit(100000)

def check(idx, target_idx, direction):
    if target_idx == len(target) - 1:
        return True

    if idx - 1 >= 0 and data[idx - 1] == target[target_idx + 1]:
        if check(idx - 1, target_idx + 1, 0):
            return True

    if direction == 1 and idx + 1 < len(data) and data[idx + 1] == target[target_idx + 1]:
        if check(idx + 1, target_idx + 1, 1):
            return True

    return False

t = int(sys.stdin.readline())
for _ in range(t):
    data = sys.stdin.readline().rstrip()
    target = sys.stdin.readline().rstrip()
    start = []

    for i in range(len(data)):
        if target[0] == data[i]:
            start.append(i)

    flag = False
    for idx in start:
        flag = check(idx, 0, 1)
        if flag:
            break

    print("YES" if flag else "NO")