Fastest Longest Common Subsequence Finder Your task is to solve the Longest Common Subsequence problem for n strings of length 1000.
A valid solution to the LCS problem for two or more strings S1, … Sn is any string T of maximal length such that the characters of T appear in all Si, in the same order as in T.
Note that T does not have to be a substring of Si.
We've already solved this problem in the shortest amount of code. This time, size doesn't matter.
Example
The strings axbycz and  xaybzc have 8 common subsequences of length 3:
abc abz ayc ayz xbc xbz xyc xyz

Any of these would be a valid solution for the LCS problem.
Details
Write a full program that solves the LCS problem, as explained above, abiding the following rules:

The input will consist of two or more strings of length 1000, consisting of ASCII characters with code points between 0x30 and 0x3F.

You have to read the input from STDIN.
You have two choices for the input format:

Each string (including the last) is followed by a linefeed.

The strings are chained together with no separator and no trailing linefeed.



The number of strings will be passed as a command-line parameter to your program.

You have to write the output, i.e., any one of the valid solutions to the LCS, to STDOUT, followed by one linefeed.

Your language of choice has to have a free (as in beer) compiler/interpreter for my operating system (Fedora 21).

If you require any compiler flags or a  specific interpreter, please mention it in your post.


Scoring
I will run your code with 2, 3, etc. strings until it takes longer than 120 seconds to print a valid solution. This means that you have 120 seconds for each value of n.
The highest amount of strings for which your code finished in time is your score.
In the event of a tied score of n, the submission that solved the problem for n strings in the shortest time will be declared the winner.
All submissions will be timed on my machine (Intel Core i7-3770, 16 GiB RAM, no swap).
The n strings of the (n-1)th test will be generated by calling rand n (and stripping the linefeeds, if requested), where rand is defined as follows:
rand()
{
    head -c$[500*$1] /dev/zero |
    openssl enc -aes-128-ctr -K 0 -iv $1 |
    xxd -c500 -ps |
    tr 'a-f' ':-?'
}

The key is 0 in the above code, but I reserve the right to change it to an undisclosed value if I suspect anybody of (partially) hardcoding the output.
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