string - 将一组字符串划分为大小大致相同的最小互斥组的算法

Question

我有一大组字符串。我想将字符串分成子集，这样:

1. 子集中的每个项目共享 1 个或多个连续字符。
2. 定义子集的共享连续字符对于子集集是唯一的(即共享字符足以定义与其他子集处于互斥关系的字符串子集)。
3. 子集的大小大致相同。
4. 生成的子集集是满足上述条件所需的最少子集数。

例如给定以下一组名称:

Alan,Larry,Alfred,Barbara,Alphonse,Carl

我可以将这个集合分成两个大小相等的子集。由连续字符“AL”定义的子集 1 将是

艾伦、阿尔弗雷德、阿尔方斯

由连续字符 ar 定义的子集 2 将是

拉里、芭芭拉、卡尔。

我正在寻找一种可以对任意一组字符串执行此操作的算法。生成的子集集不必等于 2，但它应该是最小集并且生成的子集应该近似相等。

埃利奥特

Answer 1

看看http://en.wikipedia.org/wiki/Suffix_array .可能您真正想要做的是为每个文档创建一个后缀数组，然后它们合并所有后缀数组，并带有指向原始版本的指针，以便您可以通过查找将集合作为一个字符串进行搜索将其作为数组中的后缀。