부분집합 합 알고리즘 (Longest Common SubSequence)

//Description // 문자열과 놀기를 세상에서 제일 좋아하는 영식이는 오늘도 문자열 2개의 최대 부분 공통 문자열을 구하고 있었다. // 어느 날 영식이는 조교들이 문자열 3개의 최대 부분 공통 문자열을 구하는 것을 보았다. 영식이도 도전해 보았지만 실패하고 말았다. // 이제 우리가 할 일은 다음과 같다. 영식이를 도와서 문자열 3개의 최대 부분 공통 문자열을 구하는 프로그램을 작성하라. //Input // 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. (각 문자열의 길이는 100보다 작거나 같다) //Output // 첫 줄에 첫 번째 문자열과 두 번째 문자열과 세 번째 문자열의 최대 부분 공통 문자열을 의 길이를 출력한다. //Sample Input //abcdefghijklmn //bdefg //efg //Sample Output //3

문제를 좀 더 빨리 풀기 위한 제공

=> 파일Read와 틀만 짜놨음.. 근데 이 문제가 동적 알고리즘의 예제인데… 나는 왜 재귀호출을 안쓰게 되지…ㅡ_ㅡ;;

아무튼 ㄱㄱ싱

Input.txt

namespace Longest_Common_SubSequence
{
class Program
{
const int MAX_BUF = 1024;

static void Main(string[] args)
{
string[] InputLine = FileRead();
char[] MaxChar = null;

if (InputLine.Length == 0)
return;

MaxChar = InputLine[0].ToCharArray();

Console.WriteLine("");
for(int i =0; i < MAX_BUF; i++)
{
if (InputLine[i] == null)
break;

if (InputLine[i + 1] != null)
{
MaxChar = Solve(MaxChar, InputLine[i + 1].ToCharArray());
}
}
if (MaxChar == null)
Console.WriteLine("문자열을 찾을 수가 없습니다.");
else
{
string strResult = new string(MaxChar);
Console.WriteLine("최대 문자열 : " + strResult + "\t * 갯수 : " + strResult.Length);
}

Console.ReadLine();

}

private static string[] FileRead()
{
FileStream fs = File.Open("Input.txt", FileMode.Open);
StreamReader sr = new StreamReader(fs);

string[] retVal = new string[MAX_BUF];
string line;
int nCount = 0;

while ((line = sr.ReadLine()) != null)
{
retVal[nCount++] = line;
Console.WriteLine(line);
}
sr.Close();
fs.Close();

return retVal;
}
}
}

동적 알고리즘 관련 포스트