https://codeforces.com/contest/1506/problem/C
시간 2초, 메모리 256MB

input :

• t (1 ≤ t ≤ 100)
• string a (1 ≤ |a| ≤ 20)
• string b (1 ≤ |b| ≤ 20)

output :

• For each test case, output the minimum number of operations that can make the strings a and b equal.
  각 테스트 케이스에서 a 와 b를 동일하게 만드는 최소한의 연산 횟수를 출력하시오.

조건 :

• 두 문자열이 비어있는 경우도 동일하다고 생각한다.

• 각 문자열에 대해 제일 앞에 있는 문자 혹은 제일 뒤에 있는 문자를 제거 할 수 있다.

---

이건 problem tag를 보고 나서 어떻게 할 지 생각을 했다.
그걸 보고 난 이후 다시 문제 조건을 확인했고 두 문자열의 길이가 20밖에 되지 않는다.

20짜리의 문자열에서 연속하는 부분문자열을 얻는 다면 어떤 경우가 존재할까?
20 1
19 2
18 3
17 4
...
했을 때 210개가 나온다 공식 좀 외워야 하는데 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ 모르겠다.

뭐 일단 개수가 저거 밖에 안 되기도 하는데 중복의 경우가 있을 수도 하니까 이걸 set에다가 저장을 하고 다른 문자열에 대해 이 문자열이 존재하는 지 확인하도록 하였다.

초기 값

두 문자열이 비어있는 경우도 동일하다고 보기 때문에 두 문자열 자체를 다 없애려면 자기 길이 만큼 연산을 수행해야 한다. 그래서 두 길이의 합이 초기 값이다.

그리고 어떤 문자열을 찾았다면 가장 긴 것이 그 답이 될 수 있다. 결국 최솟값을 얻는 것이기 때문이다.
각 문자열이 있다면 원래 길이에서의 차이를 통해 몇 번 연산을 했는지 알 수 있다.

import sys

for _ in range(int(sys.stdin.readline())):
    big = sys.stdin.readline().rstrip()
    small = sys.stdin.readline().rstrip()

    if len(small) > len(big):
        temp = small
        small = big
        big = temp

    words = set()
    length = len(small)
    for now in range(length, 0, -1):
        for start in range(len(small) - now + 1):
            words.add(small[start:start + now])

    pivot = len(big) + len(small)
    ans = float('inf')
    for item in words:
        if item in big and pivot - len(item) * 2 < ans:
            ans = pivot - len(item) * 2

    print(pivot if ans == float('inf') else ans)