algorithm - 高效的模式匹配/字符串合并算法

Question

我正在寻找一种用于合并字符串的算法（最好使用 java 实现）。

我的问题如下：

假设我有一个字符串数组/列表{"myString1" , "my String1" , "my-String-1" ... }值表示“ myString1 ”。

所以我想压缩我的清单。也许这可以用 KMP 来完成，或者也许有更合适的东西。

谢谢。

Answer 1

我认为编辑距离对于合并字符串是很好的启发式方法。

编辑：

您可以修改编辑距离算法：

您可以为字符 c 赋予不同的 d(-,c) 值。

所以在下面的例子中：“String1”，“String2”，你可以“惩罚”分数，但让 d(1,2) 很高，而“String 1”，“String1”则不会受到惩罚，因为分数将为 d(-,' ')。

Answer 2

或者，近似字符串匹配可能会有一些用处。我不相信 KMP 适合这个目的，因为它是为精确的子字符串匹配而设计的