[BOJ] Q5582 공통 부분 문자열

[BOJ] Q5582 공통 부분 문자열

Question

Language: Python

Difficulty: Gold 5

해당 문제는 문자열을 활용해서 풀이하는 대표적인 유형인 LCS이다.q9252문제와 매우 유사한 방향으로 문제를 풀이하면 되는데, 이때 문자가 같은 조건일때만 di 리스트를 초기화 시켜줘야한다. 이는 연속적인 공통 문자열을 구해야하기 때문이다.

아래의 LCS 알고리즘에서 else 부분의 조건문이 빠지게 되는것이다.

for i in range(1,str2_length+1):
    for j in range(1,str1_length+1):
        if str2[i-1]==str1[j-1]:
            di[i][j]=di[i-1][j-1] + 1
            max_count=max(max_count,di[i][j])
        else:
            di[i][j]=max(di[i-1][j],di[i][j-1])
            

Solution

def print_list(list):
    print("DI")
    for row in list:
        print(row)
def solution():
    str1_length=len(str1)
    str2_length=len(str2)

    di=[[0] * (str1_length+1) for _ in range(str2_length+1)]
    max_count=0
    for i in range(1,str2_length+1):
        for j in range(1,str1_length+1):
            if str2[i-1]==str1[j-1]:
                di[i][j]=di[i-1][j-1] + 1
                max_count=max(max_count,di[i][j])
    
    return max_count


if __name__ == "__main__":
    str1=list(input().strip())
    str2=list(input().strip())

    print(solution())