有趣的问题！我以前没有遇到过，所以这是我刚刚提出的一个解决方案，灵感来自 word2vec 论文所采用的方法：

1. 根据最长公共子串 (LCS) 或由字符串长度的乘积归一化的 LCS 定义成对相似度。将其缓存在矩阵中以用于考虑的任何字符串对，因为计算成本很高。还要考虑近似值。

2. 找到一个欧几里得（也许是超球面？）嵌入，以最小化误差（如果使用球，则欧几里得距离，如果使用球，则为点积）。假设随机初始化，采用基于梯度的优化方法，取误差的雅可比行列式。

3. 现在你有了一个希尔伯特空间嵌入，所以使用你选择的算法进行聚类！

对已删除评论询问如何对多个子字符串进行聚类的回应：大部分复杂性在于第一阶段；LCS的计算，所以它取决于你是否有效地做到这一点。我对遗传算法很幸运。无论如何，在这种情况下你要做的是定义一个相似向量而不是一个标量，它的元素是 k 最长的成对 LCS；有关算法，请参见此讨论。然后我将通过与每个子字符串对应的错误的总和来定义错误。

我没有解决的是如何选择嵌入的维度。word2vec 论文可能会提供一些启发式方法；看到这个讨论。我记得他们使用了相当大的空间，大约 1000 维，但他们正在优化更复杂的东西，所以我建议你从 R^2 开始，然后逐步提高。当然，您会希望对多 LCS 情况使用更高的维度。