0001 #include <cstdlib>
0002 #include <ctime>
0003 #include <cstdio>
0004 #include <string>
0005 
0006 unsigned int lcsIteration(char const * A, int n, char const * B, int m);
0007 unsigned int lcsMemoization(char const * A, int n, char const * B, int m);
0008 unsigned int lcsRecursion(char const * A, int n, char const * 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((unsigned int)time(NULL)); //随机种子
0018    //srand( 31415926 ); //固定种子（假种子，调试用） //..\..\_output\LCS\LCS.txt
0019    int errors = 0, tests = 100;
0020    for (int k = 0; k < tests; k++) {
0021       printf("\n%d\n", k);
0022       char* A; int n; char* B; int m;
0023       if (2 < argc) {
0024          m = strlen(argv[2]); B = argv[2];
0025       }
0026       else {
0027          m = 9 + rand() % 9; B = new char[m + 1];
0028          for (int j = 0; j < m; j++)
0029             B[j] = 'A' + (rand() % 26);
0030          B[m] = 0;
0031       }
0032       if (1 < argc) {
0033          n = strlen(argv[1]); A = argv[1];
0034       }
0035       else {
0036          n = 9 + rand() % 9; A = new char[n + 1];
0037          for (int i = 0; i < n; i++)
0038             A[i] = 'A' + (rand() % 26);
0039          A[n] = 0;
0040       }
0041       unsigned int lcsI = lcsIteration(A, n, B, m);
0042       unsigned int lcsM = lcsMemoization(A, n, B, m);
0043       unsigned int lcsR = lcsRecursion(A, n, B, m);
0044       errors += lcsI != lcsM || lcsM != lcsR;
0045       if ( lcsI == lcsM )
0046          printf("%2u == %2u", lcsI, lcsM);
0047       else
0048          printf("%2u <> %2u", lcsI, lcsM);
0049       if ( lcsM == lcsR )
0050          printf(" == %2u", lcsR);
0051       else
0052          printf(" <> %2u", lcsR);
0053       printf(" : %18s [%2d] ~ %18s [%2d]\n", A, n, B, m);
0054       if (argc < 3) delete[] B;
0055       if (argc < 2) delete[] A;
0056    }
0057    printf("\n%d / %d\n", tests - errors, tests);
0058    return 0;
0059 }