문제

문제
두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오.

입력
첫째 줄과 둘째 줄에 문자열이 주어진다. 문자열은 대문자로 구성되어 있으며, 길이는 1 이상 4000 이하이다.

출력
첫째 줄에 두 문자열에 모두 포함 된 부분 문자열 중 가장 긴 것의 길이를 출력한다.

정석적인 풀이를 사용하지 않아서, 풀이가 썩 괜찮은 풀이라고 생각되지는 않는다.
이 문제 한정해서는 잘 적용이 되지만, 다른 문제에도 적용하기는 힘든 풀이이다.
정석적인 풀이는 다른 블로그를 참고하자.
다른 정석적인 풀이를 보았을 때 굉장히 놀랐고 다른 문제에도 적용할 수 있으리란 생각이 들었다.

나는 긴 문자열은 고정시켜 놓고 다른 짧은 문자열을 한 칸씩 이동시키며 같은 문자의 개수를 센 후 가장 긴 것을 출력하였다.
기존의 DP와 같은 발상이지만 구현 방법에서 크게 차이가 난다.
DP는 2차원 배열을 이용하여 이전의 값을 참조한 반면, 나는 실제로 인덱스들을 조정하여 구한 것이다.
시간 복잡도는 둘이 크게 다르지 않다.

코드:

def strstr(i):
    cnt = 0
    rtn = 0
    if i < 0:
        j = -i
        i = 0
    else:
        j = 0
    while j  < len(str2):
        if str1[i] == str2[j]:
            cnt += 1
            rtn = max(rtn, cnt)
        else:
            cnt = 0
        i += 1
        j += 1
        if i >= len(str1):
            return rtn
    return rtn

str1 = list(input())
str2 = list(input())
if len(str2) > len(str1):
    tem = str1
    str1 = str2
    str2 = tem
ans = 0
for i in range(-1 * len(str2) + 1, len(str1)):
    ans = max(ans, strstr(i))
print(ans)