串对串校正算法
我不确定我是否正确地命名了这篇文章，但我想知道这种类型的算法是否有一个名称：
我想要完成的是创建一个最小指令集从一个字符串到它的排列，例如：
STACKOVERFLOW -> STAKCOVERFLOW
将需要至少一个操作，即是否
shift K before C.
有任何好的在线示例来
- 查找最小指令集（我相信这也经常出现）称为编辑距离），并
- 列出指令集
谢谢！
I'm not sure I've titled this post correctly, but I'm wondering if there's a name for this type of algorithm:
What I'm trying to accomplish is to create a minimal set of instructions to go from one string to its permutation, so for example:
STACKOVERFLOW -> STAKCOVERFLOW
would require a minimum of one operation, which is to
shift K before C.
Are there any good online examples of
- Finding the minimum instruction set (I believe this is also often called the edit distance), and
- Listing the instruction set
Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
有一种称为编辑距离的东西可以告诉您从一个字符串到另一个字符串需要进行多少次更改，并且有许多 C# 实现，还有许多其他语言。
这是维基：
http://en.wikipedia.org/wiki/Levenshtein_distance
编辑：As TheHorse已经表明，Levenshtein距离不理解Shift的变化，但是有一个改进的算法：
Damerau-Levenshtein 距离
There is something known as the Levenshtein distance that tells you how many changes are needed to go from one string to another and there are many C# implementations, many other languages too.
Here's the wiki:
http://en.wikipedia.org/wiki/Levenshtein_distance
Edit: As TheHorse has indicated, the Levenshtein distance doesn't understand Shift changes, but there is an improved algorithm:
Damerau-Levenshtein distance