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.
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.
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.
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:
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.