string - 字符串聚类-哪种算法合适？

我有一些字符串，字符不会在一个字符串中重复。
例如：“AABC”是不可能的。
我想用它们的公共子字符串把它们组合成一组。
例如：“ABC、CDF、GHP”将被分为两组
{abc，cdf}，{ghp}。
一个集合中将包含一个或多个公用子字符串的多个字符串。
与任何其他字符串没有公共子字符串的字符串将是集合本身。
所以保持最小的集合数。
例如：
1.“ABC，AHD，AKJ，LAN，WER“将是两组{ABC，AHD，AKJ，LAN}，{WER}。
2个。”abc，bdf，hlk，yht，px“将是3组{abc，bdf}.{hlk，yht}，{px}。
我认为找到一根与别人毫无共同之处的绳子很容易；

for(i=0; i< strings.num; i++)
{  str1 = strings[i];
     bool m_com=false;
     for(j=0;j < strings.num; j++ )
     {
      str2=strings[j];
      if(hascommon(str1,str2))
         m_com=true;
     }
   if(!m_com)
   {
     str1 has no common substring with any string,
   }
}

现在我在想其他的，怎么分类，有没有适合的算法呢？
输入：
字符串（字符不重复）
输出：
套（尽可能减少套数）
我知道这涉及到寻找常见的子字符串问题和集群。
但是我不熟悉聚类技术，所以我希望有人
可以给我推荐这样的算法。
虽然我在寻找好的方法来做到这一点，我也欣赏其他人的建议。
提示：实际上这些字符串是图中两点之间的简单路径。我想找到一个边缘，它的移除会切断所有这些路径。这样的边的数量应该是最小的因此，对于AB、BC、CD，这意味着存在单个路径ABCD。
我写了一个算法，在我的例子中找到公共子串（我的例子简单得多）。我想我可以在聚类过程中使用这个算法来度量相似度。
我可能有两条路径，{ABC，ADC}，删除A或删除B都可能分割路径。
或者我可以有{ABC，ADC，HG}，所以删除{A，H}，或者{CH}，或者{CG}，或者{AG}都可以。
我想我可以通过找到公共子字符串来解决这个问题，然后我决定在哪里删除边。

最佳答案

首先要指出一点：
For any two strings, "having common substring" is really equivalent to "having common letter". Thus we can replace the condition by "having common letter".
考虑顶点是字符串的图G，并且只有当两个字符串有一个公共字母时，它们才由边连接然后，您实际上要求将图G分离为连接的组件使用标准的图形运算算法c.f.the wiki page here可以很容易地实现这一点。
剩下的是建立图表的任务这也很简单：首先，创建26个标记为A到Z的框，并读取每个字符串一次如果字符串包含字母A，则将其（或其索引）放入框A，等等。最后，一个框中的这些字符串具有彼此连接的边。
可以进行进一步的优化，但我想这将取决于输入数据的性质。