Q5582. 공통 부분 문자열

연속된 문자열의 길이를 저장하며 나아가는 로직

k[i][j]의 문자를 비교하여, 같은 경우 k[i][j] = k[i-1][j-1]+1 을 합니다.

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q5582 { static int[][] dp; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); String firstString = st.nextToken(); st = new StringTokenizer(br.readLine()); String secondString = st.nextToken(); dp = new int[firstString.length()+1][secondString.length()+1]; int maxLength = 0; for (int i = 1; i <= firstString.length(); i++) { char tempChar1 = firstString.charAt(i-1); for (int j = 1; j <= secondString.length(); j++) { char tempChar2 = secondString.charAt(j-1); if (tempChar1 == tempChar2) { int length = dp[i-1][j-1]+1; dp[i][j] = length; maxLength = Math.max(maxLength, length); } } } System.out.println(maxLength); } }