代码之家 › 专栏 › 技术社区 › dreadwail

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

string algorithm c#

dreadwail · 技术社区 · 14 年前

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

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

2 回复 | 直到 14 年前

FastAl 14 年前

首先,除了至少搜索一次字符串中的每个字节(或位;-)之外,您没有其他选择。最好将它们保留为字节。然后执行 Trie (或变体)。将所有子字符串加载到trie中。节点对象应该包含标识它们属于哪个已加载数组元素的成员。然后用每个子字符串搜索它并进行匹配。

Charles Bretana 14 年前

还没有测试过这个,但它很接近吗?

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;

推荐文章

SkyWalker · 在JavaScript中,合并日期-时间序列的有效算法是什么?

1 年前

root · 计数算法

1 年前

André Silveira · 使用循环将数组的每个槽递增1。数组的大小是传递给函数的参数

2 年前

danial · 如何在多个字符串的每个位置找到最频繁的字符

2 年前

Manny · 如何比较Perl中的字符串?

2 年前

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Diret · 获取范围内每个数字的子倍数的算法

2 年前

Saif · 排序时python如何决定何时调用比较器?

2 年前

TryingToLearn · 我如何为通用遥控器构造一个类,该遥控器向连接到它的各种设备发送开/关命令?

2 年前

Sneha Sharma · 滑动窗口-在我的代码中找不到错误(非常基本的算法)

2 年前