Is there an efficient algorithm for finding a minimal common subset of pairwise distinct bits in a set of bit strings?
I am working on an efficient mapping function represented as a directed graph. In essence, it is a sort of radix trie. A path must be formed from a bit string [string hereon] efficiently. To do this, I decided on looking for and using an algorithm that finds a continuous, common subset of bits at a particular offset and length from a set of strings. I will describe the general algorithm that I seek formally as follows:
Given: $$S := \left{s_y | s_y = B_y \right}$$ $$B_y := \left{b_x | b_x\in \left{0,1\right}\right}$$ and $$s_{y,x} = B_y[x]$$ we seek to find a common subset $s_{1...|S|,p...q}$ such that $\forall\left{p, q \right}\in\Bbb{N}$, $\nexists \left{p', q' \right}\in\Bbb{N} \text{ s.t. } |p' - q'| < |p - q|$.
For the general case, the common subsets permit to find $s_{1...|S|, p_k...q_k}$. Some analysis shows that $\lceil\log_2(|S|)\rceil \leq |p - q| \leq \lfloor\log_2(s_{largest} \lor 1)\rfloor + 1$ where $s_{largest}$ is the string whose magnitude $|B_y|$ is greater than all other $|B_y|$ in $S$.
As an example algorithm for demonstration, suppose we have the following four strings, each four elements in length: $$ s_1 = \left{1, 0, 1, 1\right}\ s_2 = \left{0, 1, 0, 1\right}\ s_3 = \left{1, 1, 0, 1\right}\ s_4 = \left{1, 1, 1, 1\right} $$
We define a column thusly: $$c_{x} = s_{1...|S|,x}|x\in\Bbb{N}$$ with $c_1$ being the first column, right to left order convention, and $c_{|S|}$ being the last.
1. $p_c\leftarrow 1$. $q_c\leftarrow 0$. Column offset and (horizontal) width variables, respectively.
2. We see that the column $c_1$ is all ones, so we decide to skip it and go to $c_2$. 180
Increment $p_c$ and $q_c$.
3. $c_2$ varies, but there are only two distinct values of the four in $c_{1..2}$ read by rows. Increment $q_c$.
4. The column $c_3$ varies, and we see that there are three distinct values when read by rows, not four, so we move on to the next column. Increment $q_c$.
5. $c_4$ varies. Increment $q_c$.
6. We observe that all the columns we have, $c_{1...q_c}$, are now pairwise distinct when read by rows. Record $p_c$ and $q_c$. Terminate algorithm.
(Proof: the values read by rows interpreted as binary integers and converted to base ten read as $[5, 2, 6, 7]$.)
It's quite obvious that there is a deterministic algorithm hidden somewhere in this process using some combination of Hamming weight and XOR: for any given column, the Hamming weight of the XOR of any two columns $c_a$ and $c_b$ tells us how many unique values are represented by the common subsequence given by offset $p$ and length $q$, but I haven't yet figured out how to generalize this just to create a deterministic algorithm for all columns.
If this algorithm already exists, I do not know what it is called. For my particular implementation it would be ideal if the whole set did not have to be analyzed each time a key is added to our map, but that previous information from previous computations can be used to quickly analyze a new key and determine whether or not we need to extend the sequence again, or can keep the existing index and sequence length.
What already exists that can be implemented? If not already existing, are there any ideas on how best to proceed with an optimal algorithm as described here? 603