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