백준 5582 공통 부분 문자열

오랜만에 포스팅 하네요ㅎㅎ;;;

오늘은 DP문제를 풀었습니다.

바로 공통부분 문자열인데요 링크는 바로아래 걸어두겠습니다.

공통 부분 문자열 : www.acmicpc.net/problem/5582

5582번: 공통 부분 문자열

두문자열이 주어졌을때 두 문자열 모두에 포함된 가장긴 공통 부분 문자열의 길이를 출력하는 문제였습니다

DP문제가 관계식을 찾는게 많듯이 주어진 예제ABRACADABRA와 ECADADABRBCRDARA사이의 관계를 찾으려고 노력했습니다.

 

따라서 다음과같은 패턴을 찾을수 있었어요

아래는 다음과같은 패턴을 적용하여 코드를 구현한 부분입니다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 공통부분문자열 {

	static int[][] Arr;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String firstString = br.readLine();
		String SecondString = br.readLine();

		int firstLen = firstString.length();
		int secondLen = SecondString.length();
		int answer = 0;

		Arr = new int[firstLen][secondLen];

		for (int f = 0; f < firstLen; f++) {
			for (int s = 0; s < secondLen; s++) {
				if (firstString.charAt(f) == SecondString.charAt(s)) {
					if (outOfBound(f - 1, s - 1)) {
						Arr[f][s] = 1;
						answer = Math.max(answer, 1);
						continue;
					} else {
						Arr[f][s] = Arr[f - 1][s - 1] + 1;
						answer = Math.max(answer, Arr[f][s]);
					}
				}
			}
		}
		System.out.println(answer);
	}

	public static boolean outOfBound(int y, int x) {
		if (y < 0 || x < 0) {
			return true;
		}
		return false;
	}
}