2013年7月3日 星期三

2013/7/3 UVA 10405 - Longest Common Subsequence

/* http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=114&problem=1346&mosmsg=Submission+received+with+ID+11994527 */
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int SJ[1001][1001];
int main()
{
    char S[1001]; char J[1001];
   
    while(gets(S)!=0)
    {
        gets(J);
        int m=strlen(S);
        int n=strlen(J);
        for(int i = 0; i <= m; i++) SJ[i][0] = 0;
        for(int i = 0; i <= n; i++) SJ[0][i] = 0;
       
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
            {
                if( S[i-1] == J[j-1] ){ SJ[i][j] = SJ[i-1][j-1]+1; }
                else
                {
                    SJ[i][j] = max(SJ[i-1][j],SJ[i][j-1]);
                }
            }
       
        printf("%d\n",SJ[m][n]);
    }
}

沒有留言:

張貼留言