确定一个字符串是否是另一个字符串的前缀

Question

我写下了一个简单的函数,它确定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是给定数据集中的字符串总数.不好.

我稍微探讨了互联网,以确定最佳答案是Patricia/Radix trie.字符串存储为前缀的位置.即使这样,当我尝试插入/查找字符串时,如果我使用上述前缀测量功能,则字符串匹配会有相当大的开销.

假设我有一个前缀字符串'rom'和一组候选词

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

在基数trie中想要这样:

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

这意味着,对于每个节点,我将使用前缀匹配函数来确定哪个节点具有与索引处的前缀字符串匹配的值.不知何故,这个解决方案看起来仍然很艰巨,并不适合我.有没有更好的东西或者无论如何我可以改进核心前缀匹配功能？

Answer 1

看起来你有两个不同的问题.

一种方法是确定字符串是否包含在另一个字符串中作为前缀.为此,我建议使用已在语言的字符串库中实现的函数.在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这样的数据结构或你提到的那个似乎是要走的路.