不知道最后怎么输出，因为公共部分只输出一次。有人说回溯输出，感觉好巧妙！其实就是下图，输出的就是那条灰色的路径，但是初始时边界一定要初始化一下，因为最第一列只能向上走，第一行只能向左走。我用1表示向上走，2向左上方走，3向左走。

　　刚开始输入字符串时有两种方法，直接输入；或从地址后一位输入，即此时数组起始编号为1。直接输入时，dp[i][j]表示的是以s1[i-1],s2[j-1]为结尾LCS，另一种则就是表示以s1[i],s2[j]为结尾的LCS。两者在路径输出时有些差别，以前感觉直接输出LCS长度后者方便，其实都一样。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 const int MAXN = 107; 7 char s1[MAXN], s2[MAXN]; 8 int dp[MAXN][MAXN], flag[MAXN][MAXN]; 9 int len1, len2;10 11 void LCS()12 {13     memset(dp, 0, sizeof(dp));14     for (int i = 0; i <= len1; i++) flag[i][0] = 1;15     for (int i = 0; i <= len2; i++) flag[0][i] = 3;16     for (int i = 1; i <= len1; i++) {17         for (int j = 1; j <= len2; j++) {18             if (s1[i - 1] == s2[j - 1]) {19                 dp[i][j] = dp[i - 1][j - 1] + 1;20                 flag[i][j] = 2;21             }22             else if (dp[i - 1][j] >= dp[i][j - 1]) {23                 dp[i][j] = dp[i - 1][j];24                 flag[i][j] = 1;25             }26             else {27                 dp[i][j] = dp[i][j - 1], flag[i][j] = 3;28             }29         }30     }31 }32 33 void Print(int x, int y)34 {35     if (x == 0 && y == 0) return;36     if (flag[x][y] == 2) {37         Print(x - 1, y - 1);38         cout << s1[x-1];39     }40     else if (flag[x][y] == 1) {41         Print(x - 1, y);42         cout << s1[x - 1];43     }44     else {45         Print(x, y - 1);46         cout << s2[y - 1];47     }48 }49 50 int main()51 {52     while (cin>>s1>>s2)53     {54         len1 = strlen(s1), len2 = strlen(s2);55         LCS();56         Print(len1, len2);57         cout << endl;58     }59     return 0;60 }
        
       
      
     

起始编号为1：

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 const int MAXN = 107; 6 int dp[MAXN][MAXN], flag[MAXN][MAXN]; 7 char s1[MAXN], s2[MAXN]; 8 int len1, len2; 9 10 void LCS()11 {12     for (int i = 0; i <= len1; i++) flag[i][0] = 1;13     for(int i = 0; i <= len2; i++) flag[0][i] = 3;14     for (int i = 1; i <= len1; i++) {15         for (int j = 1; j <= len2; j++) {16             if (s1[i] == s2[j])17                 dp[i][j] = dp[i - 1][j - 1] + 1, flag[i][j] = 2;18             else if (dp[i - 1][j] >= dp[i][j - 1])19                 dp[i][j] = dp[i - 1][j], flag[i][j] = 1;20             else dp[i][j] = dp[i][j - 1], flag[i][j] = 3;21         }22     }23 }24 25 void Print(int x, int y)26 {27     if (x == 0 && y == 0) return;28     if (flag[x][y] == 2) {29         Print(x - 1, y - 1);30         printf("%c", s1[x]);31     }32     else if (flag[x][y] == 1) {33         Print(x - 1, y);34         printf("%c", s1[x]);35     }36     else {37         Print(x, y - 1);38         printf("%c", s2[y]);39     }40     return;41 }42 43 int main()44 {45     while (scanf("%s %s", s1 + 1, s2 + 1)==2)46     {47         len1 = strlen(s1 + 1), len2 = strlen(s2 + 1);48         memset(dp, 0, sizeof(dp));49         LCS();50         Print(len1, len2);51         printf("\n");52     }53     return 0;54 }