# Skillvalue Solution: Find the Link

Given a set of strings, find the longest common subtring. It is assumed that the input set of strings will never have more than one substring in common.

Input: file containing a vector of strings on each line.
Output: a string representing the common string. If the strings have no common substring, the output should be 0.

Example:

For:
orchestra
check
chelsea

The output is che (common sub-sequences are not considered valid outputs; that is, ch and he in the given example, are not considered valid outputs).

## Solution

Given only two strings, a very fast dynamic programming approach is known, which solves the problem in $$O(\ell^2)$$, where $$\ell$$ is the length of the longest string. Generalizing the problem to a finite set of strings with cardinality $$m$$ is a little harder since remembering every valid path would require a tensor and filling it would lead to a complexity of $$O(\ell^m)$$. A faster and more intuitive way of solving this problem is using a suffix-tree as well as a bit vector.

When we insert every suffix of a given string into a tree, like "orchestra", "rchestra", "chestra", ... "a" and mark every node as touched by the kth word, using a bit vector, we can start at the root node and check for the longest path for which all bits are set. Creating the tree can be done in $$O(m\cdot \ell^2)$$. We avoid the higher computational complexity by storing every combination in the tree and therefore going into space complexity. Since we expect $$\ell<32$$ we can use an integer as the bit vector and don't need to use an infinity bit set implementation like BitSet.js.

function insert(T, str, start, iter) {

for (var i = start; i < str.length; i++) {
var c = str[i];

if (T[c] === undefined) {
T[c] = {next: {}, mask: 1 << iter};
} else {
}
T = T[c].next;
}
}

var arr = ["orchestra", "check", "chelsea"];
var T = {};
for (var k = 0; k < arr.length; k++) {
var str = arr[k];
for (var i = 0; i < str.length; i++) {
insert(T, str, i, k);
}
}

Having the filled tree allows us to search for all valid substrings and extract the longest:

function findLCS(T, goal) {

var ret = [];
for (var k in T) {
}