Common Subsequence

问题:

dp问题,最长公共子串。

#define  _CODE_DHOJ_A1159_
#ifdef _CODE_DHOJ_A1159_
#include <iostream>
#include <stdio.h>
const int M = 1001;
char X[M];
char Y[M];

int dp[M][M];

inline int max(int a, int b)
{
    return a > b ? a : b;
}
void LCS()
{
   memset(dp, 0, sizeof(dp));
   for (int i = 1; i <= strlen(X); ++i)
   {
       for (int j = 1; j <= strlen(Y); ++j)
       {
           if(X[i - 1] == Y[j - 1]) 
               dp[i][j] = dp[i - 1][j - 1] + 1;
           else
               dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
       }
   }
   std::cout << dp[strlen(X)][strlen(Y)] << std::endl;
   return;
}

int main()
{
    //freopen("a1159.txt","r",stdin);
    while (scanf("%s%s",X,Y) != EOF)
    {
        LCS();
    }
    return 0;
}
#endif


Common Subsequence

上一篇:一个公司的管理之七,制度的建立需要严谨


下一篇:Humble Numbers