有效確定數組中的哪些字符串是其他字符串的子字符串？

在C＃中，假設你有一個字符串數組，其中只包含字符 '0' 和 '1'：有效確定數組中的哪些字符串是其他字符串的子字符串？

string[] input = { "0101", "101", "11", "010101011" };

你想建立一個功能：

public void IdentifySubstrings(string[] input) { ... }

那將產生如下：

"0101 is a substring of 010101011" 
"101 is a substring of 0101" 
"101 is a substring of 010101011" 
"11 is a substring of 010101011"

而你不能夠使用內置的字符串功能（如String.Substring）。

如何有效地解決這個問題？當然你可以通過暴力破解它，但它只是覺得應該有一種方法來實現它與一棵樹（因爲唯一的值是0和1，感覺像一棵二叉樹應該適合某種方式）。我已經讀了一些關於後綴樹的事情，但我不確定這是否是正確的道路。

您能想到的任何有效的解決方案？

來源

2010-06-09 Ben Lakey

這是功課？ – Oded 2010-06-09 19:43:14

或者也許是面試問題？事實上，這感覺就像我經常讓人們在進入之前回答的問題，因爲「你不能使用內置的字符串功能」部分。 – 2010-06-09 19:45:19

@Oded - 第 @Tim C - 是的，它通常用於面試問題。 – 2010-06-09 19:46:01

首先，除搜索字符串中的每個字節（或位;-)至少一次之外別無選擇。可能最好將它們保留爲字節。然後實施Trie（或變體）。將所有子字符串加載到trie中。節點對象應該包含識別它們所屬的加載數組元素的哪些元素的成員。然後用每個子字符串進行搜索並進行匹配。

來源

2010-06-09 19:48:25 FastAl

通過暴力方法的性能增益會在這裏簡單地說，一旦你到達葉節點，你可以確信你的測試字符串不是其他任何字符串的子字符串？ – 2010-06-09 20:03:26

關於這個答案的更多想法：我認爲這會起作用並且效率很高，但我認爲它不會識別從0以外的位置開始的子字符串。例如，我不認爲它會將「101」識別爲是「0101」的子字符串。 – 2010-06-09 20:17:56

這是正確的，你將不得不改變使用trie。一個快速的方法 - 例如，從第二個字節開始添加每個子字符串。當然這會讓你馬上掉到o（n^2），所以你必須有一個比這個更精巧的變體。困難的問題，祝你好運。 – FastAl 2010-06-09 20:31:58

沒有測試過這一點，但就是它接近

var string2FindLen = string2Find.Length; 
var ndx = 0; 
var x = string2Find[ndx]; 
foreach(var c in string2LookIn) 
{ 
    if (ndx == string2FindLen) return true; 
    if (c==x) x = string2Find[++ndx]; 
    else ndx = 0; 
} 
return false;

來源

2010-06-09 19:56:37

你可能誤解了這個問題;你的解決方案只能看到一個字符串是否是另一個字符串的子字符串，而不是N個字符串中的N個字符串。 – 2010-06-09 20:02:01

有效確定數組中的哪些字符串是其他字符串的子字符串？

回答

相關問題