如何以最佳方式返回短语是否已出现在单词流中

Question

有一股巨大的单词流。随着单词的不断出现，可以要求它判断已经看到的流中是否出现了短语在不同的时间可能有多个这样的查询

例如，假设到目前为止看到的单词流是：

你好，这里是另一位程序员

然后，它被要求判断短语here is another是否被看到，在这种情况下是真的。

如何以最佳方式返回？

我一直在尝试使用图的构造和在查询时进行BFS来解决问题，但它带来了两个问题：

• 首先，为了优化，我还必须将图对中节点的words=>地址存储在哈希表中。

• 第二，当有循环时，算法失败，如流中所示：a b c d a b c e

为需求提出最佳解决方案。

Answer 1

您可以查找"后缀树的在线构建"，并找到Ukkonen的一种算法，该算法处理一个流，并且在处理完每个字符后，始终为您的流准备一个后缀树，如果到目前为止您已经看到n个字符，则运行时间和空间为O（n）。然后，每次给你一个查询短语时，你都可以使用后缀树的子串匹配算法来查找给定查询短语的所有匹配项，如果你的查询短语长度为m，那么查询时间是最优的O（m）来查找匹配项。

Answer 2

因为您正在以流式方式接收要搜索的文本正文，所以对文本进行"预处理"以提高搜索效率是没有意义的。这里是C#中的一个高效实现，它以流的方式处理要搜索的文本。

static IEnumerable<int> Search(string text, string query)
{
    var D = new Dictionary<int, int>();
    //Loop invariant: D[i] == j iff text[i..(i+j)] == query[0..j]
    //                for all pairs (i,j) in D
    for (int i = 0; i < text.Length; i++)
    {
        foreach (var k in D.Keys.ToList())
        {
            D[k] = D[k] + 1;
            if (D[k] == query.Length)
            {
                yield return k;
                D.Remove(k);
            }
            else if (text[i] != query[D[k]])
            {
                D.Remove(k);
            }
        }
        if (text[i] == query[0])
            D.Add(i, 0);
    }
    foreach (var k in D.Keys)
    {
        if (D[k] == query.Length)
            yield return k;
    }
}

基于流的版本可以实现如下。我认为流结束的情况可能处理得不好，但即使在边缘情况下，您也应该能够将想法调整为有效的想法。

class SearcherState
{
    public Dictionary<int, int> D = new Dictionary<int, int>();
    public int i = 0;
}
static Func<char, int?> Searcher(string query)
{
    var state = new SearcherState();
    return c =>
    {
        int? result = null;
        foreach (var k in state.D.Keys.ToList())
        {
            state.D[k] = state.D[k] + 1;
            if (state.D[k] == query.Length)
            {
                result = k;
                state.D.Remove(k);
            }
            else if (c != query[state.D[k]])
            {
                state.D.Remove(k);
            }
        }
        if (c == query[0])
            state.D.Add(state.i, 0);
        state.i++;
        return result;
    };
}