55821 [Java] BOJ 5582번 공통 부분 문자열 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 풀이 DP를 사용하여 해결했습니다. 문제에서 나온 1번 예시를 풀어보면 ABRACA~ 를 S1이라 하고 인덱스는 i, ECADA~ 를 S2라 하고 인덱스는 j라고 한다면 S1[i] == S2[j]라면 이전까지 연속되는 부분 문자열에 새로 공통된 문자가 들어가므로 S1과 S2에 공통되는 이전 문자인 memo[i -1][j - 1]에 저장된 길이에 + 1을 하여 즉, memo[i -1][j - 1] + 1을 현재 위치에서 공통되는 연속된 부분 문자열인 m.. 2021. 7. 13. 이전 1 다음