高效的数据结构字符串搜索？ [英] Efficient Data Structure For Substring Search?

问题描述

假设我有一组串S和查询串Q。我想知道如果S的任何成员为q的子串。 （对于这一疑问子的目的包括平等，如富是富的子串）。例如，假设该函数，我想要做什么叫做 anySubstring

Assume I have a set of strings S and a query string q. I want to know if any member of S is a substring of q. (For the purpose of this question substring includes equality, e.g. "foo" is a substring of "foo".) For example assume the function that does what I want is called anySubstring:

S = ["foo", "baz"]
q = "foobar"
assert anySubstring(S, q)  # "foo" is a substring of "foobar"

S = ["waldo", "baz"]
assert not anySubstring(S, q)

有没有容易实现算法与时间复杂度次线性为此在 LEN（S）？这是确定若S首先必须加工成一些聪明的数据结构，因为我会查询每个有很多q字符串s，因此这preprocessing的摊余成本可能是合理的。

Is there any easy-to-implement algorithm to do this with time complexity sublinear in len(S)? It's ok if S has to be processed into some clever data structure first because I will be querying each S with a lot of q strings, so the amortized cost of this preprocessing might be reasonable.

编辑：为了澄清，我不介意的这的S成员为q的子串，只有是否至少有一个是。换句话说，我的仅关心一个布尔答案。

To clarify, I don't care which member of S is a substring of q, only whether at least one is. In other words, I only care about a boolean answer.

推荐答案

我觉得阿霍Corasick算法你想要做什么。我认为还有另一种解决方案是非常简单的工具，它的<一个href="http://en.wikipedia.org/wiki/Karp-Rabin#Rabin.E2.80.93Karp_and_multiple_pattern_search">Karp-Rabin算法。

I think Aho-Corasick algorithm does what you want. I think there is another solution which is very simple to implement, it's Karp-Rabin algorithm.

这篇关于高效的数据结构字符串搜索？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！