如何以最佳方式返回短語是否出現在單詞流中？

Question

有一串話來了，這是非常大的。隨着單詞不斷出現，可能會要求您告知是否在已經看到的流中發生了短語？ 在不同的時間可能有多個這樣的查詢。

例如，假設看到到現在的話流是：

你好這裏的世界是另一個程序員

然後，它要求告訴短語here is another是否已經看到或不，在這種情況下是這樣。

如何優化返回？

我一直試圖在使用圖形的建設和查詢時做BFS解決工作，但它帶來了兩個問題：

• 首先，是最佳的，我也有存儲話=>圖中的節點地址對在一個散列表中。

• 其次，當存在循環，那麼算法失敗作爲流中：a b c d a b c e

推薦爲需求的最佳解決方案。

Answer 1

您可以查看「在線構建後綴樹」，並找到一個由Ukkonen處理流的算法，並且在每個字符處理完成後，您的流總是有一個後綴樹，並且運行時間和空間爲O（ n）如果你迄今看過n個字符。然後，每次給出查詢短語時，都可以使用子字符串匹配算法爲後綴樹查找給定查詢短語的所有匹配，並且如果查詢短語具有長度，則查詢時間爲最佳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; 
    }; 
}