UVA 10405 Longest Common Subsequence

题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_problem&problem=1346

Dynamic programming

需要注意的是input里可能含有空行，一行空行也是一个string，所以如果用scanf("%s", string)是不能把空行存进string变量里的。需要用gets或者getline来处理input。

可惜的是我目前对于gets，getline的用法还没有很熟悉，之后会关于这方面的区别做解释。又或者有大神可以帮忙讲解一下，感恩

代码如下：

 #include <iostream>

 #include <math.h>

 #include <stdio.h>

 #include <cstdio>

 #include <algorithm>

 #include <string.h>

 #include <cstring>

 #include <queue>

 #include <vector>

 #include <functional>

 #include <cmath>

 #define SCF(a) scanf("%d", &a)

 #define IN(a) cin>>a

 #define FOR(i, a, b) for(int i=a;i<b;i++)

 typedef long long Int;

 using namespace std;

 int main()

 {

     char str1[];

     char str2[];

     int len1, len2;

     while (cin.getline(str1, ))

     {

         cin.getline(str2, );

         for (len1 = ; str1[len1] != '\0'; len1++);

         for (len2 = ; str2[len2] != '\0'; len2++);

         int** match;

         match = new int*[len1+];

         FOR(i, , len1 + )

             match[i] = new int[len2 + ];

         FOR(i, , len1 + )

             match[i][] = ;

         FOR(i, , len2 + )

             match[][i] = ;

         FOR(i, , len1 + )

         {

             FOR(j, , len2 + )

             {

                 if (str1[i - ] == str2[j - ])

                     match[i][j] = match[i - ][j - ] + ;

                 else

                 {

                     match[i][j] = max(match[i - ][j], match[i][j - ]);

                 }

             }

         }

         printf("%d\n", match[len1][len2]);

         FOR(i, , len1 + )

             delete[] match[i];

         delete[]  match;

     }

     return ;

 }