动态规划之一--求两个字符串的最大相同串(包括断开的)

/*
  Name: Longest common subsequence
  Date: 29-11-07 16:13
  Description: 求两个字符串的最大相同串(包括断开的)
  例:s1:abcdef
     s2: ceh
     则结果为 ce
     s1:ACCGGTCGAGTGCGCGGAAGCCGGCCGAA
     s2:GTCGTTCGGAATGCCGTTGCTCTGTAAA
     结果:GTCGTCGGAAGCCGGCCGAA
    
    采用的方法为动态规划,参考<算法导论>
*/

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#define MAX 60
const char* INPUT_FILE = "lcs.txt";
const char* OUTPUT_FILE = "lcs_re.txt";

int    b[MAX][MAX]; //1:west 2:northwest 3:north

int    c[MAX][MAX];

FILE *in,*out;

void LCS_length(char *s1,char *s2);
void print_lcs(char *s,int i,int j);

void LCS_length(char *s1,char *s2)
{
    int m,n,i,j;

    m = strlen(s1);
    n = strlen(s2);

    for(i = 1;i <= m ;i ++)
        c[i][0] = 0;
    for(j = 0;j <= n ;j ++)
        c[0][j] = 0;
    for(i = 1;i <= m;i ++)
        for(j = 1;j <= n; j ++)
        {
            if(s1[i-1] == s2[j-1])
            {
                c[i][j] = c[i-1][j-1] + 1;
                b[i][j] = 2;
            }
            else if(c[i-1][j] >= c[i][j-1])
            {
                c[i][j] = c[i-1][j];
                b[i][j] = 3;
            }
            else
            {
                c[i][j] = c[i][j-1];
                b[i][j] = 1;
            }

        }
}

void print_lcs(char *s,int i,int j)
{
    if(i == 0 || j == 0)
        return;
    if(b[i][j] == 2)
    {
        print_lcs(s,i-1,j-1);
        fputc(s[i-1],out);
    }
    else if(b[i][j] == 3)
        print_lcs(s,i-1,j);
    else
        print_lcs(s,i,j-1);
}

int main()
{
     int   i