[python] 백준 5582 공통 부분 문자열

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

5582번: 공통 부분 문자열

 

문제 해결

• for문으로 우선 서로 알파벳이 맞는 것을 찾아야겠다는 생각을 했다. (다만 이중 for문이면 시간초과 나지 않을까? 생각했는데 python3에서는 시간초과가 났다. pypy3를 써야한다.)
• 조금 특이했던 것은 문장 길이를 구하는 것이기 때문에 dp[i][j]를 string1 i번째 알파벳과 string2 j번째 알파벳이 같은데 앞에서부터 이어진 최대 길이라고 생각하면 된다. 따라서 앞에 dp[i-1][j-1]이 0이면 string1 i-1번째와 string2 j-1번째 알파벳이 다르다는 의미로 dp[i][j]=1이 되고 dp[i-1][j-1]이 양수이면 그 수만큼 이어져온 것이므로 dp[i][j] = dp[i-1][j-1]+1이 된다.

CODE

string1 = str(input().rstrip())
string2 = str(input().rstrip())
answer = 0
dp = [[0]*(len(string2)+1) for _ in range(len(string1)+1)]

for i in range(1,len(string1)+1):
    for j in range(1,len(string2)+1):
        if string1[i-1] == string2[j-1]:
            dp[i][j] = dp[i-1][j-1]+1
            answer = max(dp[i][j],answer)
print(answer)