5582
-
[백준]5582: 공통 부분 문자열 - JAVA문제풀이/백준 2021. 6. 1. 10:53
[백준]5582: 공통 부분 문자열 https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 풀이 문제 이름에 맞게 "공통 부분 문자열"을 구하는 문제이다. LCS랑 비슷해 보이지만 약간 다르다. LCS는 부분 수열이 되는 수열 중 가장 긴 수열을 찾는 것이고, 이 문제는 공통 부분 문자열 중에 가장 긴 수열을 찾는 것이다. 두 이론의 차이는 예를 들어 다음과 같다. str1이 ABC이고 str2가 AC일때 LCS를 구하면 2가되며 LCS는 ..