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

Question

在 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，所以感觉就像二叉树应该以某种方式适合)。我读过一些关于后缀树之类的东西，但我不确定这是否是正确的路径。

你能想到什么有效的解决方案？

Answer 1

首先，您别无选择，只能在搜索字符串中的每个字节(或位；-)至少一次。可能最好将它们保留为字节。然后执行 Trie (或变体)。将所有子字符串加载到 trie 中。节点对象应包含标识它们属于加载的数组元素的成员。然后用每个子字符串搜索它并进行匹配。