4

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

我在 Internet 上进行了一些探索，以确定最佳答案是 Patricia/​​Radix trie。字符串存储为前缀的位置。即使那样，当我尝试插入/查找字符串时，如果我使用上述前缀测量功能，字符串匹配也会有相当大的开销。

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

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

在 radix trie 中会这样：

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

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

4

2 回答 2

10

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

一种是确定一个字符串是否作为前缀包含在另一个字符串中。为此，我建议使用该语言的字符串库中已经实现的函数。在 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 这样的数据结构或者你提到的那个似乎是要走的路，如果你想要快速查找的话。

于 2013-09-04T03:45:49.837 回答
1

在stackoverflow上查看这个线程 -如何检查一个字符串“StartsWith”是否是另一个字符串？. Mark Byers 的解决方案似乎非常有效。对于 Java，还有内置的字符串函数“endsWith”和“startsWith” - http://docs.oracle.com/javase/tutorial/java/data/comparestrings.html

于 2013-09-04T05:45:35.697 回答