Fastest Longest Common Subsequence Finder
C, n = 3 in ~7 seconds

Algorithm

The algorithm is a direct generalization of the standard dynamic programming solution to n sequences. For 2 strings A and B, the standard recurrence looks like this:

L(p, q) = 1 + L(p - 1, q - 1)           if A[p] == B[q]
        = max(L(p - 1, q), L(p, q - 1)) otherwise


For 3 strings A, B, C I use:

L(p, q, r) = 1 + L(p - 1, q - 1, r - 1)                          if A[p] == B[q] == C[r]
           = max(L(p - 1, q, r), L(p, q - 1, r), L(p, q, r - 1)) otherwise


The code implements this logic for arbitrary values of n.

Efficiency

The complexity of my code is O(s ^ n), with s the length of the strings. Based on what I found, it looks like the problem is NP-complete. So while the posted algorithm is very inefficient for larger values of n, it might actually not be possible to do massively better. The only thing I saw are some approaches that improve efficiency for small alphabets. Since the alphabet is moderately small here (16), that could lead to an improvement. I still predict that nobody will find a legitimate solution that goes higher than n = 4 in 2 minutes, and n = 4 looks ambitious already.

I reduced the memory usage in the initial implementation, so that it could handle n = 4 given enough time. But it only produced the length of the sequence, not the sequence itself. Check the revision history of this post for seeing that code.

Code

Since loops over n-dimensional matrices require more logic than fixed loops, I'm using a fixed loop for the lowest dimension, and only use the generic looping logic for the remaining dimensions.

#include &lt;stdint.h&gt;
#include &lt;string.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;stdio.h&gt;

#define N_MAX 4

int main(int argc, char* argv[]) {
    int nSeq = argc - 1;
    if (nSeq &gt; N_MAX) {
        nSeq = N_MAX;
    }

    char** seqA = argv + 1;

    uint64_t totLen = 1;
    uint64_t lenA[N_MAX] = {0};
    uint64_t offsA[N_MAX] = {1};
    uint64_t offsSum = 0;
    uint64_t posA[N_MAX] = {0};

    for (int iSeq = 0; iSeq &lt; nSeq; ++iSeq) {
        lenA[iSeq] = strlen(seqA[iSeq]);
        totLen *= lenA[iSeq] + 1;

        if (iSeq + 1 &lt; nSeq) {
            offsA[iSeq + 1] = totLen;
        }

        offsSum += offsA[iSeq];
    }

    uint16_t* mat = calloc(totLen, 2);
    uint64_t idx = offsSum;

    for (;;) {
        for (uint64_t pos0 = 0; pos0 &lt; lenA[0]; ++pos0) {
            char firstCh = seqA[0][pos0];
            int isSame = 1;
            uint16_t maxVal = mat[idx - 1];

            for (int iSeq = 1; iSeq &lt; nSeq; ++iSeq) {
                char ch = seqA[iSeq][posA[iSeq]];
                isSame &amp;= (ch == firstCh);

                uint16_t val = mat[idx - offsA[iSeq]];
                if (val &gt; maxVal) {
                    maxVal = val;
                }
            }

            if (isSame) {
                mat[idx] = mat[idx - offsSum] + 1;
            } else {
                mat[idx] = maxVal;
            }

            ++idx;
        }

        idx -= lenA[0];

        int iSeq = 1;
        while (iSeq &lt; nSeq &amp;&amp; posA[iSeq] == lenA[iSeq] - 1) {
            posA[iSeq] = 0;
            idx -= (lenA[iSeq] - 1) * offsA[iSeq];
            ++iSeq;
        }
        if (iSeq == nSeq) {
            break;
        }

        ++posA[iSeq];
        idx += offsA[iSeq];
    }

    int score = mat[totLen - 1];

    char* resStr = malloc(score + 1);
    resStr[score] = '\0';

    for (int iSeq = 0; iSeq &lt; nSeq; ++iSeq) {
        posA[iSeq] = lenA[iSeq] - 1;
    }

    idx = totLen - 1;
    int resIdx = score - 1;

    while (resIdx &gt;= 0) {
        char firstCh = seqA[0][posA[0]];
        int isSame = 1;
        uint16_t maxVal = mat[idx - 1];
        int maxIdx = 0;

        for (int iSeq = 1; iSeq &lt; nSeq; ++iSeq) {
            char ch = seqA[iSeq][posA[iSeq]];
            isSame &amp;= (ch == firstCh);

            uint16_t val = mat[idx - offsA[iSeq]];
            if (val &gt; maxVal) {
                maxVal = val;
                maxIdx = iSeq;
            }
        }

        if (isSame) {
            resStr[resIdx--] = firstCh;
            for (int iSeq = 0; iSeq &lt; nSeq; ++iSeq) {
                --posA[iSeq];
            }
            idx -= offsSum;
        } else {
            --posA[maxIdx];
            idx -= offsA[maxIdx];
        }
    }

    free(mat);

    printf("score: %d\n", score);
    printf("%s\n", resStr);

    return 0;
}


Instructions for Running

To run:


Save the code in a file, e.g. lcs.c.
Compile with high optimization options. I used:

clang -O3 lcs.c


On Linux, I would try:

gcc -Ofast lcs.c

Run with 2 to 4 sequences given as command line arguments:

./a.out axbycz xaybzc


Single quote the command line arguments if necessary, since the alphabet used for the examples contains shell special characters.


Results

test2.sh and test3.sh are the test sequences from Dennis. I don't know the correct results, but the output looks at least plausible.

$ ./a.out axbycz xaybzc
score: 3
abc

$ time ./test2.sh 
score: 391
16638018802020&gt;3??3232270178;47240;24331395?&lt;=;99=?;178675;866002==23?87?&gt;978891&gt;=9&lt;6&lt;9381992&gt;&gt;7030829?255&gt;6804:=3&gt;:;60&lt;9384=081;0:?66=51?0;5090724&lt;85?&gt;&gt;:2&gt;7&gt;3175?::&lt;9199;5=0:494&lt;5&lt;:7100?=95&lt;91&gt;1887&gt;33&gt;67710==;48&lt;&lt;327::&gt;?78&gt;77&lt;6:2:02:&lt;7=5?:;&gt;97&lt;993;57=&lt;&lt;=:2=9:8=118563808=962473&lt;::8&lt;816&lt;464&lt;1==925&lt;:5:22?&gt;3;65=&gt;=;27?7:5&gt;==3=4&gt;&gt;5&gt;:107:20575347&gt;=48;&lt;7971&lt;&lt;245&lt;??219=3991=&lt;96&lt;??735698;62?&lt;98928

real  0m0.012s
user  0m0.008s
sys   0m0.003s

$ time ./test3.sh 
score: 269
662:2=2::=6;738395=7:=179=96662649&lt;&lt;;?82?=668;2?603&lt;74:6;2=04=&gt;6;=6&gt;=121&gt;1&gt;;3=22=3=3;=3344&gt;0;5=7&gt;&gt;7:75238;559133;;392&lt;69=&lt;778&gt;3?593?=&gt;9799&lt;1&gt;79827??6145?7&lt;&gt;?389?8&lt;;;133=505&gt;2703&gt;02?323&gt;;693995:=0;;;064&gt;62&lt;0=&lt;97536342603&gt;;?92034&lt;?7:=;2?054310176?=98;5437=;13898748==&lt;&lt;?4

real  0m7.218s
user  0m6.701s
sys   0m0.513s