有效确定数组中的哪些字符串是其他字符串的子字符串？

在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

有效确定数组中的哪些字符串是其他字符串的子字符串？

回答

相关问题