题意：两个字符串结合起来，公共的字符只输出一次

分析：LCS，记录每个字符的路径

 

代码：

/*    LCS(记录路径)模板题：            用递归打印路径:)*/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int N = 1e2 + 10;const int INF = 0x3f3f3f3f;char s[N], t[N];int dp[N][N];int fa[N][N];void print(int x, int y)　　{    if (!x && !y)   return ;    if (fa[x][y] == 0)  {        print (x-1, y-1);    printf ("%c", s[x-1]);    }    else if (fa[x][y] == -1)    {        print (x-1, y);    printf ("%c", s[x-1]);    }    else    {        print (x, y-1);    printf ("%c", t[y-1]);    }}void LCS(void)  {    int lens = strlen (s), lent = strlen (t);    memset (dp, 0, sizeof (dp));    memset (fa, 0, sizeof (fa));    for (int i=0; i<=lens; ++i)    fa[i][0] = -1;    for (int i=0; i<=lent; ++i)    fa[0][i] = 1;    for (int i=1; i<=lens; ++i) {        for (int j=1; j<=lent; ++j) {            if (s[i-1] == t[j-1])   {                dp[i][j] = dp[i-1][j-1] + 1;                fa[i][j] = 0;            }            else if (dp[i-1][j] >= dp[i][j-1])  {                dp[i][j] = dp[i-1][j];                fa[i][j] = -1;            }            else    {                dp[i][j] = dp[i][j-1];                fa[i][j] = 1;            }        }    }    // printf ("%d\n", dp[lens][lent]);    print (lens, lent); puts ("");}int main(void)  {    while (scanf ("%s %s", &s, &t) == 2)    {        LCS ();    }    return 0;}