Самая короткая уникальная подпоследовательность, которая отличает набор строк

Question

У меня есть N строк бит (каждый из размеров M) X1 [0..M], ..., XN [0..M]. Мне нужен псевдокод/​​алгоритм, чтобы найти наименьшую длину подпоследовательности (не обязательно непрерывную), которая уникальна в каждой заданной строке. Например,

Если строки имеют номер 011011, 011000, 010010, то подпоследовательность [2,4] (11, 10, 01) различается в каждой строке. Или подпоследовательность [2, 4, 5] (111, 100, 010). Или подпоследовательность [4, 5] (11, 00, 10).
Но не подпоследовательность [0, 1, 5] (011, 010, 010) ---> Не уникально в каждой строке.

EDIT: 1 <= M <= 1000, 2 <= N <= 10.
EDIT: В настоящее время мое решение таково: Минимальная длина подпоследовательности будет находиться в диапазоне между ceil(log2(N)) и N-1. Таким образом, псевдокод будет:

for i = ceil(log2(N)) to N-1 : 
    check all subsequence of size i 
    if any subsequence distinguish all N strings, return i 

Первый шаг может быть сделано путем генерации всех комбинаций MCI. Второй шаг можно сделать, извлекая подпоследовательность для всех N строк и проверяя, все ли они различны. Но этот алгоритм в настоящее время является экспоненциальной сложностью. Я хотел знать, возможен ли лучший алгоритм.

EDIT: Нет, это не домашнее задание. Это было задано в интервью.

Answer 1

я думаю, что что-то подобное будет работать:

первый:

create matriz A (mxm) and array B(m) 
for each bit i from right to left, compute de decimal value of j word in A[i][j] 
//that means A[i][j] holds the decimal value of word j until the i bit 
in the same loop B[i] will hold if bit i from all words are the same. 

если B [я] = верно, то это означает, что мы не должны смотреть эту позицию, потому что это ничего не говорит.

create deque D//to check if there is equal elements 
create array C(m) 
for each position P in [0...M] where B[i] = false : 


for each bit i = P ... 0 

    for each word j 
     C[j] = C[j]*2 + word[j][i] //word[j][i] = word j in bit i 

    bool finished = true; 
    for each e in C: 
     if(D.count(e) > 0) { 
      finished = false; 
      break; 
     } 
     else{ 
      D.add(e) 
     } 
    } 
    if(finished) return range(P...i); 
    D.clear() 

not possible; 

, что этот алгоритм делает: начиная с полезных позиций, он начинает создавать значение слова из них, и в тот момент, вы можете добавить их все в деке (все они различны), вам нужно найти диапазон, в котором они отличаются (диапазон - P - i + 1).

Вы должны запустить это в любом случае для всех i, где B [i] = false, поэтому в худшем случае он должен работать около n³.

Обратите внимание, что есть некоторые оптимизации, которые можно выполнить, зная количество строк и их размер, например: если есть 10 строк размера 3, вы знаете, что невозможно отличить (при этом существуют разные 10 разных двоичных файлов 3 Размер). Учитывая количество строк, вы можете искать только для (смежных или нет) размеров ceil (log (количество строк)). Например, 5 слов can not отличаются в одном бите, также они не могут отличаться в 2 битах, но с 3 битами они могут отличаться.