[BOJ] C++ 5582 공통 부분 문자열 - LCS와 유사한 문제

5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 예제 ABRACADABRA ECADADABRBCRDARA ans : 5 ------------------------------ UPWJCIRUCAXIIRGL SBQNYBSBZDFNEV ans : 0 LCS와 유사하지만 이 문제는 공통부분 문자열이 연속되어야 한다는 점이 다르다. 예를 들어 ABCD와 ABDC의 공통부분 문자열 중 BD는 존재하지 않는다. 풀이는 처음부터 LCS를 고려하고 생각했다. 그 외의 방법은 떠오르지도 않아서 일단 LCS처럼 2차..

2023.09.09