Определите, является ли одна строка префиксом другой

Я написал простую функцию, которая определяет, является ли str1 префиксом str2. Это очень простая функция, которая выглядит так (в JS):

function isPrefix(str1, str2) // determine if str1 is a prefix of a candidate string
{
    if(str2.length < str1.length) // candidate string can't be smaller than prefix string 
        return false;

    var i = 0;
    while(str1.charAt(i) == str2.charAt(i) && i <= str1.length)
        i++;
   if(i < str1.length) // i terminated => str 1 is smaller than str 2
        return false;
    return true;
}

Как видите, он проходит по всей длине строки префикса, чтобы определить, является ли он префиксом строки-кандидата. Это означает, что его сложность равна O(N), что неплохо, но это становится проблемой, когда у меня есть огромный набор данных, чтобы рассмотреть возможность циклического прохождения, чтобы определить, какие строки имеют строку префикса как часть префикса. Это усложняет сложность, например, O(M*N), где M - общее количество строк в данном наборе данных. Нехорошо.

Я немного изучил Интернет, чтобы определить, что лучшим ответом будет "Патрисия / Радикс". Где строки хранятся в виде префиксов. Даже тогда, когда я пытаюсь вставить / посмотреть строку, при сопоставлении строк будут существенные издержки, если я использую вышеупомянутую функцию измерения префикса.

Скажем, у меня была префиксная строка "rom" и набор слов-кандидатов

var dataset =["random","rapid","romance","romania","rome","rose"];

это было бы так в корне:

         r
       /    \
     a       o
    / \     / \
ndom pid  se  m
             / \
           an   e
          /  \
        ia   ce

Это означает, что для каждого узла я буду использовать функцию сопоставления префиксов, чтобы определить, какой узел имеет значение, соответствующее строке префикса в индексе. Так или иначе, это решение все еще кажется трудным и не устраивает меня. Есть ли что-то лучше, или в любом случае я могу улучшить функцию соответствия префикса ядра?

Источник

2 ответа

Решение

Похоже, у тебя две разные проблемы.

Один из них - определить, содержится ли строка в качестве префикса в другой строке. Для этого я бы предложил использовать функцию, уже реализованную в строковой библиотеке языка. В JavaScript вы могли бы сделать это

if (str2.indexOf(str1) === 0) {
    // string str1 is a prefix of str2
}

См. Документацию для String.indexOf здесь: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/indexOf

Для другой проблемы, в связке строк, выясните, какие из них имеют заданную строку в качестве префикса, построение структуры данных, такой как Trie или та, которую вы упомянули, кажется подходящим, если вы хотите быстрый поиск.

Источник

Проверьте этот поток на stackru - Как проверить, если строка "StartsWith" другой строки?, Решение Mark Byers представляется очень эффективным. Также для Java есть встроенные строковые функции "конец-с" и "начинается-с" - http://docs.oracle.com/javase/tutorial/java/data/comparestrings.html

Источник
Другие вопросы по тегам