求一个算法：一个字符串变成另一个字符串的编辑过程

[hellogbk]

我在寻找这个算法的过程中找到了 edit distance算法，不过跟我需要的东西不是太一样。
具体的要求就是，给出两个字符串（当然这两个字符串都不会太长，而且一般都会有一定的相似性，当然也有可能完全不相似）

比如：
原始字符串：this is a strings.
目标字符串：This is not a damn string.

算法要求能够整理说从原始字符串到目标字符串所需要的编辑过程。
比如说：
1. 删掉原句开头小写的t
2. 在开头插入大写的T
3. 在某某位置处插入not
4. 在某某位置插入damn
5. 删掉某某位置的字母s

求大神帮忙！！！当然最好是JAVA写的。
多谢！

[Kilerd]

- this is a strings.
+ This is not a damn string.

Git 的做法 ←_←

[hellogbk]

@Kilerd 呃好吧， 我需要的是一个详细的编辑过程呀。。。

[Hyperion]

从收藏夹里翻出了这个：
http://article.yeeyan.org/view/67953/33055

[Kilerd]

@hellogbk 详细算法，就是伸手党了。。。。。

[msg7086]

https://leetcode.com/problems/edit-distance/

其实就是Edit Distance，只不过原题是以字母为单位，而你这是可以把字母合并成词为单位。

[pimin]

1.原句拆分,str1="this is a strings.";str2="This is not a damn string.";
拆分成单词词组,words1={"this","is","a","strings"}
1.首字母强制大写转换,
2.找到合适的位置插入你想要插入的单词,比如判断在is,are,之类be动词前后做处理.如果没有怎么处理.
3.重新拼接

[binux]

你没看懂 edit distance，这东西就是 edit distance

[aheadlead]

编辑距离＋1
可以从dp的结果上反推

[qiayue]

知乎的编辑日志就是这样

[qiayue]

@pimin 你不能仅仅根据楼主举的这个例子来写算法

[jsq2627]

就是编辑距离。基本的DP问题，建议好好理解下自己解决。

[zmj1316]

这个我们上数据结构课用过，记得是用LCS做的；好像是从后往前扫；反正是个DP问题

[shiye515]

http://yujiangshui.com/javascript-levenshtein-distance/

[faceair]

不是叫 Operational Transformation 的么？

[jugelizi]

以前用最大公共子字符串比较的