假设我有一个字符串集合:
- constitution
- abracadabra
- refrigerator
- stackoverflow
现在我有一个"损坏"的句子,其中可以找到集合中字符串的重要子串,但没有特定顺序或具体数量。这些单词的分隔也不一定明显。
有什么算法能帮我在损坏的句子中找到集合中最可能出现的字符串?
这是一个示例输入:
xbracadabrqbonstitution ibracadabrefrigeratos obracadabri xtackoverflotefrigeratos
从这个输入中,我期望能够重构出以下已知单词的数组:
['abcracadabra', 'constitution', 'abracadabra', 'refrigerator', 'abracadabrea', 'stackoverflow', 'refrigerator']
句子非常短(通常只有5-6个单词),因此可以使用占用内存和计算资源较多的算法。而且,损坏总是局限于每个单词的前几个和后几个字符;中间总是正确的(这就是为什么我要寻找大的子串的原因)。
有什么想法吗?由于单词不是明显分开的,因此普通的编辑距离不能解决问题。