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

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"];

在Radix trie中，它会像这样显示：

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

这意味着，对于每个节点，我将使用前缀匹配函数来确定哪个节点具有与索引处前缀字符串匹配的值。不过，这种解决方案仍然似乎很费力，并且让我感到不太满意。是否有更好的方法或者我可以改进核心前缀匹配函数？

- Parijat Kalia

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或您提到的数据结构似乎是快速查找的方法。

- Ram

---

标记为正确，因为它比我的前缀匹配解决方案好得多，而那是主要问题，而不是数据结构，另外因为你需要一些分数，迫切需要@Ram :) - Parijat Kalia

哦，是吗？你迫切需要一些Hadoop！:P - Ram

那个解决方案不是很低效吗？如果一个字符串是另一个字符串的前缀，你必须在第一个不匹配处停止。然而，indexOf将尝试对str2的每个字符进行相同的检查。 - ABu

Answer 2

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

- jaykhopale