Найти наименьшую уникальную подстроку для каждой строки в массиве
(Я пишу это в контексте JavaScript, но соглашусь с алгоритмически правильным ответом на любом языке)
Как вы найдете кратчайшую подстроку каждого элемента в массиве строк, где подстрока НЕ содержится внутри любого из других элементов, игнорируя случай?
Предположим, что у меня есть входной массив, например:
var names = ["Anne", "Anthony", "LouAnn", "Kant", "Louise", "ark"];
Результат должен выглядеть примерно так:
var uniqueNames = ["ne", "h", "ua", "ka", "i", "r"];
В моих целях вы можете с уверенностью предположить, что ни один элемент не будет полностью содержаться внутри другого элемента.
Мои мысли:
Кажется, что, возможно, это было бы грубой силой, по строкам:
var names = ["Anne", "Anthony", "LouAnn", "Kant", "Louise", "ark"];
var uniqueNames = [], nameInd, windowSize, substrInd, substr, otherNameInd, foundMatch;
// For each name
for (nameInd = 0; nameInd < names.length; nameInd++)
{
var name = names[nameInd];
// For each possible substring length
windowLoop:
for (windowSize = 1; windowSize <= name.length; windowSize++)
{
// For each starting index of a substring
for (substrInd = 0; substrInd <= name.length-windowSize; substrInd++)
{
substr = name.substring(substrInd,substrInd+windowSize).toLowerCase();
foundMatch = false;
// For each other name
for (otherNameInd = 0; otherNameInd < names.length; otherNameInd++)
{
if (nameInd != otherNameInd && names[otherNameInd].toLowerCase().indexOf(substr) > -1)
{
foundMatch = true;
break;
}
}
if (!foundMatch)
{
// This substr works!
uniqueNames[nameInd] = substr;
break windowLoop;
}
}
}
}
Но я должен представить себе более элегантное решение, использующее файлы try/prefix, массивы суффиксов или что-то интересное.
Edit:
Я считаю, что это форма, которую выбранный ответ будет программно использоваться в JavaScript:
var names = ["Anne", "Anthony", "LouAnn", "Kant", "Louise", "ark"];
var uniqueNames = [], permutations = {}, permutation, nameInd, windowSize, substrInd, substr;
// For each name
for (nameInd = 0; nameInd < names.length; nameInd++)
{
var name = names[nameInd];
// For each possible substring length
windowLoop:
for (windowSize = 1; windowSize <= name.length; windowSize++)
{
// For each starting index of a substring
for (substrInd = 0; substrInd <= name.length-windowSize; substrInd++)
{
substr = name.substring(substrInd,substrInd+windowSize).toLowerCase();
permutations[substr] = (typeof permutations[substr] === "undefined")?nameInd:-1;
}
}
}
for (substr in permutations)
{
permutation = permutations[substr];
if (permutation !== -1 && ((typeof uniqueNames[permutation] === "string" && substr.length < uniqueNames[permutation].length) || typeof uniqueNames[permutation] === "undefined"))
{
uniqueNames[permutation] = substr;
}
}
Ответы
Ответ 1
Скажите N - количество строк, а L - максимальная длина строки. Вы выполняете итерации N*L*L*N.
Я могу только немного улучшить его, торгуя одной итерацией для дополнительной памяти. Для каждой возможной длины подстроки (L итераций),
-
перечислить все подстроки этой длины в каждом имени (N*L) и сохранить их среди индекса имени в хэш-таблицу (1). Если для этой подстроки уже есть индекс, вы знаете, что это не сработает, тогда вы замените индекс специальным значением, например -1.
-
Пройдите хэш-таблицу, подбирая подстроки, для которых индекс не является -1 - это ответы для соответствующих индексов, но используйте их только в том случае, если эти имена еще не имеют более короткого ответа от предыдущей итерации
Использование памяти может быть значительно уменьшено путем хранения ссылки обратно в существующую строку вместо копирования подстрок.
Ответ 2
Эта проблема может быть решена в сложности O (N * L * L * L). В этом подходе будут использоваться попытки суффикса. Каждый node of the trie также будет хранить счетчик префикса, который будет ссылаться на количество раз, когда сформированная подстрока при перемещении к этому node из корня появилась во всех суффиксах, вставленных до сих пор.
Мы будем создавать попытки N + 1. Первое три будет глобальным, и мы будем вставлять в него все суффиксы всей строки N. Следующие N попытки будут локальными для каждой строки N, содержащей соответствующие суффиксы.
Этот шаг предварительной обработки построения попыток будет выполнен в O (N * L * L).
Теперь, как только попытки были построены, для каждой строки мы можем начать запрашивать количество раз, когда подстрока (начиная с минимальной длины) имела место в глобальном trie и trie, соответствующем этой строке. Если это то же самое в обоих, то это означает, что он не включен ни в какие другие строки, кроме самого себя. Этого можно достичь в O (N * L * L * L). Сложность может быть объяснена как N для каждой строки L * L для рассмотрения каждой подстроки и L для выполнения запроса в trie.
Ответ 3
Если вы создадите обобщенное дерево суффикса, вам просто нужно найти неглубокую точку, в которой инфикс каждой строки отделяется от инфикс других строк и присваивает метку этой точке ветвления плюс один "отличительный" символ, Кикер состоит в том, что должен быть такой дополнительный символ (он может отделяться только от метасимвола, застрявшего в конце каждой строки), а точка разветвления может не привести к листу, это может привести к поддереву с листьями все из одной строки (поэтому необходимо учитывать внутренние узлы).
Для каждой строки S найдите самую мелкую (по глубине родительской метки) node N, которая содержит только листья из S, а метка кромки - по крайней мере один символ. Метка пути от корня до родителя N плюс один символ из метки кромки, ведущей к N, является кратчайшим инфишированием S, не найденным в других строках.
Я считаю, что маркировка узлов, содержащих только листья из одной строки, может быть выполнена во время построения или путем O (N) сканирования GST; то просто проверить сканирование последнего дерева и сохранить минимальный уровень для каждой строки. Так что все O (N).
(изменить - я еще не могу ответить на комментарии)
Чтобы уточнить, каждый суффикс в дереве суффиксов имеет node, где он отделяется от других суффиксов; целью здесь является найти суффикс /a для каждой строки, которая отходит от суффиксов всех остальных строк на минимальной глубине, как измеряется меткой пути к этому значению node. Все, что нам нужно, это один дополнительный символ после этой точки, чтобы иметь подстроку, которая не отображается ни в какой другой строке.
Пример:
Строки: abbc, abc
Используя алгоритм Уконена, после первой строки мы имеем дерево суффикса только суффиксов из этой строки; Я назову их [1] здесь:
abbc[1]
b
bc[1]
c[1]
c[1]
Затем мы вставляем суффиксы строки 2:
ab
bc[1]
c[2]
b
bc[1]
c
[1]
[2]
c
[1]
[2]
Теперь мы хотим найти кратчайшую строку, которая ведет к ветке с только [1] под ней; мы можем сделать это, просмотрев все [1] и посмотрев на их непосредственных родителей, которые я перечислю здесь по метке пути, плюс один символ (который я буду использовать ниже):
abbc: abb
bbc: bb
bc: bc[1]
c: c[1]
Обратите внимание, что я включил [1], поскольку это метасимвол, который отличает идентичные суффиксы [1] и [2]. Это удобно при определении подстрок, которые повторяются в нескольких строках, но это не полезно для нашей проблемы, так как если мы удалим [1], мы получим строку, которая также встречается в [2], т.е. Это не кандидат.
Теперь ни одна из ярлыков справа не встречается в любой другой строке, поэтому мы выбираем самую короткую, не включая метасимвол, который является bb.
Аналогично, вторая строка имеет следующие кандидаты:
abc: abc
bc: bc[2]
c: c[2]
Только один не имеет метасимвола в конце, поэтому нам нужно перейти с помощью abc.
Моим последним моментом является то, что этот минимальный поиск по строке не должен происходить один раз в раз; GST можно отсканировать один раз, чтобы обозначить узлы как содержащие листы из одной строки ([1], [2],.. [n]) или "смешанные", а затем минимальные неразрешенные строки в строке (я бы называть эти "отличительные инфикс" ) также можно рассчитать за один проход.
