[Baekjoon] 5582_공통 부분 문자열

Gold V

문제(출처: https://www.acmicpc.net/problem/5582)

---

< 공통 부분 문자열 >

 

문제 풀이 

 

배열 2개를 사용해서 공통부분 문자열을 구한다.

 

만약 abcd와 bacd라면 아래와 같이 만들어지도록 구현한다.

	a	b	c	d
b	0	1	0	0
a	1	0	0	0
c	0	0	1	0
d	0	0	0	2

 

 

 my solution (Java)

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

public class _5582_ { // 공통 부분 문자열

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

		String a = bf.readLine();
		String b = bf.readLine();

		int arr[][] = new int[a.length() + 1][b.length() + 1];

		int result=0;

		for (int i = 0; i < a.length(); i++) {
			for (int j = 0; j < b.length(); j++) {
				if(a.charAt(i)==b.charAt(j)) {
					arr[i+1][j+1]=arr[i][j]+1;
					result=Math.max(arr[i+1][j+1], result);
				}
			}
		}
		System.out.println(result);
	}
}

변수)
a, b : 두 문자열
arr : 부분 문자열의 길이 저장
result : 가장 긴 부분 문자열

 

두 문자열을 전체 순환하면서 문자가 같다면 전 값에 +1을 한 값을 저장한다. 문자가 같을 때마다 가장 긴 부분 문자열의 값을 바꿔준다.

---

---