求一个字符串差异比较算法

给出源字符串和目标字符串，要比较出相对于源字符串，目标字符串在哪里插入了字符，在哪里删除了字符。  
  如str1="abcde";str2="acd2ef";  
  要知道曾经删除b并插入了2和f。 问题点数：100、回复次数：8Top

1 楼independently（我是风筝高高飞）回复于 2006-03-18 12:13:09 得分 20

首先你提的需求是不够明确，我举个例子，例如源字符串是"abcdefg",目标字符串是"abcdmdeefg",这当中可能经过了几个转换：1直接在源字符串中d字符后插入mde；2、在源字符串中d字符后插入md后，再在源字符串中e字符后插入字符e。这样的话就没法实现你的要求。在检测过程中，如果遇到类似的问题，得有个优先级问题。看你怎么取舍了Top

2 楼serversql（啊初）回复于 2006-03-18 12:22:49 得分 20

循环str1，在str2查找，如果没有   就是删除掉了  
  循环str2，在str1查找，如果没有   就是添家了  
  还可以知道是哪个位置  
  不过，字符串不要太长！Top

3 楼independently（我是风筝高高飞）回复于 2006-03-18 12:28:51 得分 20

楼上的，不能那样啊，可能有很多重复的字符，不能那么草率判断的！Top

4 楼mademelaugh（五朝臣子(以接分为荣，以不结帖为耻)）回复于 2006-03-18 14:01:38 得分 0

To:independently(我是风筝高高飞)    
  我不需要比较过程以及细节，只需要比较最终的差异。如果要排优先级，肯定是从前往后去尽量大的相同部分了。Top

5 楼wuyazhe（wyz&xyl）回复于 2006-03-18 14:08:43 得分 20

尝试改良kmp。每次判断主串当前剩下的字串的最大重复位置，再这之前的认为是插入或修改的部分。回头有兴趣的可以写一下。应该蛮有趣。Top

6 楼independently（我是风筝高高飞）回复于 2006-03-18 14:31:21 得分 10

恩。本来想写一个呢，可惜电脑坏啦，要到周一才能修。在用别人的电脑，没有编程工具Top

7 楼lxjlz（）回复于 2006-03-18 14:33:57 得分 10

upTop

8 楼mademelaugh（五朝臣子(以接分为荣，以不结帖为耻)）回复于 2006-03-20 18:20:28 得分 0

已解决，lcs问题Top

相关问题

• 字符
• 字符串
• 插入
• 删除
• 目标
• 问题
• str

• 帖主：mademelaugh
• independently
• serversql
• independently
• wuyazhe
• independently
• lxjlz

• CSDN .NET频道
• .NET类图书
• C#类图书
• .NET类源码下载