검색어 입력폼
평가점수B

[알고리즘,algorithm,lcs] 최대공통문자열(Longest Common Subsequence)

등록일 2003.11.23 파일확장자압축파일 (zip) | 7페이지 | 가격 500원

소개글

동적 프로그래밍 방법으로 Longest Common Subsequence 를 찾는 알고리즘 입니다.
VC++ 에서 작성했으며 사용한 데이타 파일도 함께 포함되어 있습니다.

목차

1.개요
2.문제접근과정
3.수행결과 및 걸린시간
4.소스코드
5.토의
6.참고자료

본문내용

# Longest Common Subsequence

1. 개요
- text1, text2 두 파일에서 공통적으로 들어있는 가장 큰 문자열을 찾는다.
- 문자열 검색시 줄바꿈(CR) 은 고려하지 않는다.
- alphabet 이외의 다른 문자들도 검색에 포함.

2. 문제 접근 과정
문제해결을 위해 우선 교재에 있는 Longest Common Subsequence를 보고 2차원 배열을 만들어 해결하는 방법을 생각했다. Dynamic Programming 에 의한 해결방법으로 문자열 text1 과 text2 가 있을때 text1 의 길이를 A, text2 의 길이를 B 라고 하고 각각의 인덱스를 i, j 또한 LCS(text1[i],text2[j])를 text1 의 i 번째까지와 text2 의 j 번째까지를 비교한 LCS 라고 하면 text1[i]==text2[j] 일때 text1[i] 는 LCS 에 포함된다.
text1[i]와 text2[j]가 다를때 LCS(text1[i+1],text2[j]) 과 LCS(text1[i],text2[j+1])을 비교하여 더 큰 문자열이 LCS 가 된다.

참고 자료

Algorithms(Thomas H. Cormen)
다운로드 맨위로