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       } else {
0026          m = 9 + rand() % 9; B = new char[m + 1];
0027          for (int j = 0; j < m; j++)
0028             B[j] = 'A' + (rand() % 26);
0029          B[m] = 0;
0030       }
0031       if (1 < argc) {
0032          n = strlen(argv[1]); A = argv[1];
0033       } else {
0034          n = 9 + rand() % 9; A = new char[n + 1];
0035          for (int i = 0; i < n; i++)
0036             A[i] = 'A' + (rand() % 26);
0037          A[n] = 0;
0038       }
0039       unsigned int lcsI = lcsIteration( A, n, B, m );
0040       unsigned int lcsM = lcsMemoization( A, n, B, m );
0041       unsigned int lcsR = lcsRecursion( A, n, B, m );
0042       errors += lcsI != lcsM || lcsM != lcsR;
0043       if ( lcsI == lcsM )
0044          printf("%2u == %2u", lcsI, lcsM);
0045       else
0046          printf("%2u <> %2u", lcsI, lcsM);
0047       if ( lcsM == lcsR )
0048          printf(" == %2u", lcsR);
0049       else
0050          printf(" <> %2u", lcsR);
0051       printf(" : %18s [%2d] ~ %18s [%2d]\n", A, n, B, m);
0052       if ( argc < 3 ) delete[] B;
0053       if ( argc < 2 ) delete[] A;
0054    }
0055    printf("\n%d / %d\n", tests - errors, tests);
0056    return 0;
0057 }