[백준] 5582 공통부분 문자열, python(pypy)

https://www.acmicpc.net/problem/5582

5582번: 공통 부분 문자열

pypy에선 되는데 python에선 시간초과와 메모리 초과가 뜬다. python에서 하려면 다른 방법으로 접근해야한다.

문자 테이블을 만들어서 두 문자열을 비교했다.

비교하는 알파벳이 같으면 1로 체크하고, 같지 않으면 0으로 체크한다.

체크하면 이렇게 된다.

여기서 공통부분 문자(1이 체크된 것)에서 대각선 방향으로 가장 긴 배열찾으면된다.

길이를 알아야하므로 memoization을 실행할때 공통문자이고, 대각선 위의 값이 1이상이면 대각선 값+1 로 갱신한다

갱신한 값은 이렇게된다.

위의 테이블에서 최대값을 찾으면 최대길이가 나온다.

import sys; input = sys.stdin.readline

def main():
    str1, str2 = input().rstrip(), input().rstrip()
    answer = 0
    memo = [[0 for _ in range(len(str1) + 1)] for _ in range(len(str2) + 1)]
    for r in range(1, len(str2) + 1):
        for c in range(1, len(str1) + 1):
            if str2[r - 1] == str1[c - 1]:
                memo[r][c] = memo[r - 1][c - 1] + 1
                answer = max(answer, memo[r][c])
            else:
                memo[r][c] = 0
    print(answer)

if __name__ == '__main__':
    main()