查找按字符索引分组的多个字符串的并集算法

Question

我一直试图想出一种性能有效的方法,可以在一组fixed width按索引分组的字符串中查找字符出现的并集.像这样的东西;

s1 = "013965"
s2 = "015935"
s3 = "310012"

导致以下内容,其中每个数字组都存在于char index n的所有字符串中:

out = "[03][1][350][90][631][52]"

我已经想过以非常天真的方式迭代每个字符串,在每个索引处,同时将中间字符串存储在一个数组中,然后遍历该数组以构建输出值.然而,在我看来,我的方法是一种非常低效的方法,与渐近最优解决方案相差太远.

Answer 1

如果预先知道所有可能字符的集合，假设它们的数量是n，并且n不是太高（例如 10，如果您只处理数字），则可以通过创建m长度为 的布尔数组来做到这一点n，m其中输入字符串中的位置数或数字 和n。true如果第 n 个字符出现在任何输入字符串的第 m 个位置中，则第 m 个数组中的第 n 个位置将为。False将表示，之前没有这样的字符位于第 m 个位置。

然后你可以迭代每个字符串，当你n在位置遇到字符时，你可以在第 m 个数组的第 n 个位置m进行标记。true最后，你将得到m数组，每个数组描述第 m 组的内容

pos[0] = {true, true, false, false, false, true, true, false, true, false}
pos[1] = {true, false, false, false, false, false, false, false, false, false}
pos[2] = {false, false, true, true, false, false, false, false, false, true}

翻译为

[0,1,5,6,8] [0] [2,3,9]

由于所有结构都是直接访问数组，因此不涉及查找，所有访问都在恒定时间内进行，并且只需访问每个字符一次，不涉及比较。希望这可以帮助。