Эффективное определение того, какие строки в массиве являются подстрока других?

Question

В C #, скажем, у вас есть массив строк, которые содержат только символы '0' и '1':

string[] input = { "0101", "101", "11", "010101011" };

И вы хотите построить функцию:

public void IdentifySubstrings(string[] input) { ... }

Это приведет к следующему:

"0101 is a substring of 010101011"
"101 is a substring of 0101"
"101 is a substring of 010101011"
"11 is a substring of 010101011"

И вы НЕ способны использовать встроенную функциональность строк (например, String.Substring).

Как эффективно решить эту проблему?Конечно, вы можете пропустить это с помощью грубой силы, но просто кажется, что должен быть способ выполнить это с помощью дерева (поскольку единственными значениями являются 0 и 1, кажется, что двоичное дерево должно как-то соответствовать).Я немного читал о таких вещах, как суффиксные деревья, но я не уверен, что это правильный путь, чтобы идти вниз.

Какие эффективные решения вы можете придумать?

Answer 1

Прежде всего, у вас нет выбора, кроме каждого байта (или бита ;-) в искомой строке хотя бы один раз.Вероятно, лучше оставить их в байтах.Затем реализуйте Trie (или вариант).Загрузите все подстроки в три.Объекты узла должны содержать элементы, идентифицирующие, к какому из загруженных элементов массива они принадлежат.Затем найдите его с каждой подстрокой и сделайте свои совпадения.

Answer 2

Не проверял это, но оно близко

var string2FindLen = string2Find.Length;
var ndx = 0;
var x = string2Find[ndx];
foreach(var c in string2LookIn)
{
    if (ndx == string2FindLen) return true;
    if (c==x) x = string2Find[++ndx];
    else ndx = 0;
}
return false;