×¹«¹²×ÓÐòÁÐ

AC´úÂ룺

#include<iostream>
#include<cstring>
using namespace std;
int c[100][100] = { 0 }, b[100][100] = { 0 };
int i, j, m, n;
void LCS(char *x, char *y, int m, int n)
{
 for (i = 0; i <= m; i++)
  c[i][0] = 0;
 for (i = 0; i <= n; i++)
  c[0][i] = 0;
 for (i = 1; i <= m; i++)
  for (j = 1; j <= n; j++)
  {
   if (x[i] == y[j])
   {
    c[i][j] = c[i - 1][j - 1] + 1;
    b[i][j] = 0;
   }
   else if (c[i - 1][j] >= c[i][j - 1])
   {
    c[i][j] = c[i - 1][j];
    b[i][j] = 1;
   }
   else {
    c[i][j] = c[i][j - 1];
    b[i][j] = 2;
   }

  }
}
void printLCS(char *x, int b[100][100], int i, int j)
{
 if (i == 0 || j == 0) return;
 if (b[i][j] == 0)
 {
  printLCS(x, b, i - 1, j - 1);
  cout << x[i];
 }
 else if (b[i][j] == 1)
 {
  printLCS(x, b, i - 1, j);
 }
 else if (b[i][j] == 2)
 {
  printLCS(x, b, i, j - 1);
 }

}
int main()
{
 char x[100], y[100];
 cin >> x +1;
 cin >> y +1;
 m = strlen(x) ;
 n = strlen(y) ;
 LCS(x, y, m, n);
 printLCS(x, b, m, n);
 return 0;

}

ÍƼöÇ廪´óѧ Ëã·¨·ÖÎöÓëÉè¼Æ¹«¿ª¿Î