0001 #include <cstdlib>
0002 #include <ctime>
0003 #include <cstdio>
0004 #include <string>
0005 
0006 uint32_t lcsDP(const char* A, int n, const char* B, int m);
0007 uint32_t lcsM0(const char* A, int n, const char* B, int m);
0008 uint32_t lcsR(const char* A, int n, const char* B, int m);
0009 
0010 /******************************************************************************************
0011  * Longest Common Subsequence
0012  * Example test cases:
0013  *    HNAJBJDJU   LDVFGDKD
0014  *    ZEIEZCCTPZ   WPUZALLPBXL
0015  ******************************************************************************************/
0016 int main(int argc, char* argv[]) {
0017    srand(31415926); //srand((uint32_t) time(nullptr)); //随机种子
0018    int errors = 0, tests = 100;
0019    for (int k = 0; k < tests; k++) {
0020       printf("\n%d\n", k);
0021       char* A; int n; char* B; int m;
0022       if (2 < argc) {
0023          m = strlen(argv[2]); B = argv[2];
0024       } else {
0025          m = 9 + rand() % 9; B = new char[m+1];
0026          for (int j = 0; j < m; j++)
0027             B[j] = 'A' + (rand() % 26);
0028          B[m] = 0;
0029       }
0030       if (1 < argc) {
0031          n = strlen(argv[1]); A = argv[1];
0032       } else {
0033          n = 9 + rand() % 9; A = new char[n+1];
0034          for (int i = 0; i < n; i++)
0035             A[i] = 'A' + (rand() % 26);
0036          A[n] = 0;
0037       }
0038       uint32_t lcs_i = lcsDP(A, n, B, m);
0039       uint32_t lcs_m = lcsM0(A, n, B, m);
0040       uint32_t lcs_r = lcsR(A, n, B, m);
0041       errors += lcs_i != lcs_m || lcs_m != lcs_r;
0042       if (lcs_i == lcs_m)
0043          printf("%2u == %2u", lcs_i, lcs_m);
0044       else
0045          printf("%2u <> %2u", lcs_i, lcs_m);
0046       if (lcs_m == lcs_r)
0047          printf(" == %2u", lcs_r);
0048       else
0049          printf(" <> %2u", lcs_r);
0050       printf(" : %18s [%2d] ~ %18s [%2d]\n", A, n, B, m);
0051       if (argc < 3) delete[] B;
0052       if (argc < 2) delete[] A;
0053    }
0054    printf("\n%d / %d\n", tests - errors, tests);
0055    return 0;
0056 }