算法最短preFIX匹配？ [英] Algorithm for shortest prefix matching?

问题描述

由于串P和字符串列表找到其中p为preFIX最短的字符串。

Given String p and list of strings find the shortest string for which p is the prefix.

我知道蛮力方法，但是这将是最佳的方法？

I know the brute force approach but what will be the optimal approach?

例如。

p = "foo bar"
list = {"foo bar 1",
        "foo bar foo bar",
        "bar foo foo foo bar bar"};

应该返回富吧1

Should return "foo bar 1"

推荐答案

如果您已经有一个搜索空间（在你的情况下，相对恒定的列表），然后生成一个线索或其他合适的结构将有助于搜索了很多。开始维基百科这也解释了这一点足够的细节，让你开始：

If you already have a search space (in your case, a relatively constant list), then generating a trie or some other suitable structure would help searching a lot. Start with Wikipedia which explains this in enough detail to get you started:

• http://en.wikipedia.org/wiki/Trie

下面是从使用的话上面的文章（这很容易地扩展到使用任何类型的字符串，甚至非字符串）图像：

Here's an image from the above article that uses words (which readily extends to using strings of any kind or even non-strings):

本文提供了一些性能比较与其他合适的结构，这将有利于你的情况。

The article provides some performance comparisons with other suitable structures, which is helpful in your case.

请注意，如果列表更改，必须足够，那么这种方式的收益可能会减少，或者你甚至可以有更差的表现相比，蛮力。

Note that if list changes sufficiently enough, then the returns of this approach might diminish or you can even have worse performance compared to brute-force.

这篇关于算法最短preFIX匹配？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！