算法，用于将一组字符串到的最小集合相互排斥的组的大小大致相同(Algorithm for divid

我有一个大组字符串。 我想将字符串分成子集，即：

1. 在一个子集中的每个项目股1个或更多个连续字符。
2. 定义的子集共享的连续字符是对于该组子集（即，共享字符是足够用于定义串的一个子集，代表与其它子集互斥关系）是唯一的。
3. 该子集是大致相同的尺寸。
4. 将得到的子集的集合是适合上述标准所需子集的最小数目。

例如，给定下面的一组名字：

艾伦，拉里，阿尔弗雷德，芭芭拉，阿方斯·卡尔

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

艾伦，阿尔弗雷德·阿尔方斯

子集2由连续的字符AR将被定义

拉里·芭芭拉，卡尔。

我在寻找一种算法，将字符串的任意一组这样做。 将得到的子集的集合不必等于2，但它应该是最低的组，将所得的子集应大致相等。

埃利奥特

Answer 1:

看一看http://en.wikipedia.org/wiki/Suffix_array 。 这可能是你真正想要做的是为每个文件后缀阵列，并将它们合并所有后缀阵列，指针回原来的版本，这样就可以通过查看搜索的集合为一个字符串为它作为在阵列中的后缀。

Answer 2:

这是棘手。 我不知道是否有一些更高的目标（如Word索引）或者这只是一个学术问题？

这不是一般的解，除非你接受空序列（其中发生在所有的话）中定义的一组的平凡解。 例如，取串： a ， ab ， b 。

1. a必须进入通过定义的集合a 。
2. b必须进入通过定义的集合b 。
3. ab必须进入这两个，因为它包含两个子序列。

将一个类似的例子发生的那种，你要处理的话吗？ 我不知道。 也许你可以处理的话映射到一组以上的，或者你可以有一个打破平局系统，以确定在哪里把它。

假设这不是一个问题， Burrows-Wheeler变换可能会找到好的子帮助。

或者怎么样是这样的：

1. 产生在单词的所有序列。
2. 建立子序列的干扰图，其中连接两个子如果它们都发生在一个单一的字的边缘。
3. 色图。
4. 挑选每种颜色代表序列。
5. 请各代表子定义的一组。 如果该颜色的所有单词有子，把他们都变成那一套。
6. 否则，删除，从图中串，并从第3步重复。

这种算法可能破裂，但它可能给你一个解决的一些想法（或你的问题;-)的trickiness至少一些想法。

文章来源: Algorithm for dividing a set of strings into a minimum set of mutually exclusive groups roughly the same size