求字符串差异比较算法
给出源字符串和目标字符串，要比较出相对于源字符串，目标字符串在哪里插入了字符，在哪里删除了字符。
如str1="abcde";str2="acd2ef";
要知道曾经删除b并插入了2和f。
问题点数：100、回复次数：16Top
1 楼san_126（阿三）回复于 2006-03-18 15:17:57 得分 10
要比较出相对于源字符串，目标字符串在哪里插入了字符，在哪里删除了字符。
如str1="abcde";str2="acd2ef";
.............................................
这个也太麻烦了吧,删除和插入的字符有可能是重复的......你限定条件没说清楚
如str1 = "abcde",要用删除和插入的方法而得到str2的方法无限多......
比如你先删除str1中的bcde,然后再插入cde2ef
也可能是你先插入不相关的任意字符串,然后再删除,那就无解了Top
2 楼skywoody（）回复于 2006-03-18 15:23:48 得分 30
其实可以找出两个字符串的最大子列，然后就可以看出哪些是相同的
哪里改变了
具体参看算法导论
以下是参考算法导论写的一个LCS算法
稍加修改应该可以为你所用
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
using namespace std;
//
// Parameters
//
// first1: An input iterator addressing the position of the first element
// of the 1st sequence.
//
// last1: An input iterator addressing the position one past the last
// element of the 1st sequence.
//
// first2: An input iterator addressing the position of the first element
// of the 2nd sequence.
//
// last2: An input iterator addressing the position one past the last
// element of the 2nd sequence.
//
// result: An output iterator addressing the first element in the
// destination range where the LCS is to be stored.
//
// Return Value
//
// The length of the LCS.
//
template<
class InputIterator1
, class InputIterator2
, class OutputIterator
>
size_t
longest_common_subsequence( InputIterator1 first1
, InputIterator1 last1
, InputIterator2 first2
, InputIterator2 last2
, OutputIterator result )
{
size_t size1 = ( size_t )distance( first1, last1 );
size_t size2 = ( size_t )distance( first2, last2 );
//
// dynamic programming for the length of the LCS
//
vector<vector<size_t> > len( size1 + 1, vector<size_t>( size2 + 1, 0 ) );
InputIterator1 it1 = first1;
for( size_t i = 1; i <= size1; i++, ++it1 ) {
InputIterator2 it2 = first2;
for( size_t j = 1; j <= size2; j++, ++it2 )
if( *it1 == *it2 )
len[ i ][ j ] = len[ i - 1 ][ j - 1 ] + 1;
else
if( len[ i - 1 ][ j ] >= len[ i ][ j - 1 ] )
len[ i ][ j ] = len[ i - 1 ][ j ];
else
len[ i ][ j ] = len[ i ][ j - 1 ];
}
//
// trace back for the LCS
//
typedef typename InputIterator1::value_type value_type;
vector<value_type> lcs;
size_t i = size1, j = size2, k = len[ size1 ][ size2 ] - 1;
lcs.reserve( k + 1 );
while( i && j ) {
value_type& v1 = *( first1 + i - 1 );
value_type& v2 = *( first2 + j - 1 );
if( len[ i ][ j ] == len[ i - 1 ][ j - 1 ] + 1 && v1 == v2 ) {
lcs.push_back( v1 );
i--; j--; k--;
}
else
if( len[ i - 1 ][ j ] > len[ i ][ j - 1 ] )
i--;
else
j--;
}
copy( lcs.rbegin(), lcs.rend(), result );
return len[ size1 ][ size2 ];
}
int main( void ) {
string s1 = "ABCBDAB", s2 = "BDCABA", lcs;
cout
<< "LCS length is "
<< longest_common_subsequence( s1.begin()
, s1.end()
, s2.begin()
, s2.end()
, back_inserter<string>( lcs ) )
<< endl;
copy( lcs.begin(), lcs.end(), ostream_iterator<char>( cout ) );
cout << endl;
return 0;
}
Top
3 楼newpine（）回复于 2006-03-18 15:29:03 得分 3
你 的问题根本就没有描述清楚。就你举的例子：如str1="abcde";str2="acd2ef";
要知道曾经删除b并插入了2和f。。难道就不能这样理解吗 :str2曾经删除了cd2ef，并插入了bcde。。，
关键是要看你要达到什么的效果，这个是可以斟酌的。Top
4 楼jixingzhong（瞌睡虫·星辰）回复于 2006-03-18 16:05:46 得分 10
这个问题 ...
通过比较，
可以知道两个字符串有些什么不一样的 ～
至于是插入还是删除，
看看不同的字符是在哪个串中，
如果在 源串中，
那么就是被删除的字符，
插入的么，就是在 目标串中的差异字符了 ...
Top
5 楼jixingzhong（瞌睡虫·星辰）回复于 2006-03-18 16:08:04 得分 7
注意上面说的差异字符
不仅要考虑字符的值，
还要考虑字符的个数的 ～Top
6 楼yinqing_yx（淘汰引擎)(玩虚一族）回复于 2006-03-18 16:11:13 得分 3
这个问题位置问题怎么才能准确解决
比如
str1 = "eeeeeeeeee"
str2 = "eeeeeeeee"
哪个位置删的~
除非在改动的时候就进行位置确定~Top
7 楼mademelaugh（五朝臣子(以接分为荣，以不结帖为耻)）回复于 2006-03-18 16:31:40 得分 0
不好意思没有说清楚。其实就是文件比较的意思，只不过我我要直接比较字符串而已。就是比较最终的差异。对于yinqing_yx(淘汰引擎) 说的相同字符产生的位置问题，我不需要这种精度，当然能达到最好了。
楼上各位所提的建议和提供的代码，我先看看。谢谢各位！！Top
8 楼du51（郁郁思扬）回复于 2006-03-18 17:09:47 得分 3
就是比较最终的差异?
这是什么意思?
就是指两个字符串都什么不同吗?
以位对齐说吗?Top
9 楼mademelaugh（五朝臣子(以接分为荣，以不结帖为耻)）回复于 2006-03-18 21:41:27 得分 0
。。。越描越糊涂了。
Top
10 楼ruodeer（看我的个性签名都给我分）回复于 2006-03-19 10:22:57 得分 3
+UTop
11 楼yjm0105（流云）回复于 2006-03-19 10:27:38 得分 3
给2个没关系的文件，用你的描述比较后，应该是什么结果？Top
12 楼mademelaugh（五朝臣子(以接分为荣，以不结帖为耻)）回复于 2006-03-20 10:51:20 得分 0
其实就是lcs问题。好在待比较的字符不会很长，也不会到文件级别的地步去。
谢谢skywoody，不知道还有没有别的算法实现。Top
13 楼creative55（hansonlu）回复于 2006-03-20 15:14:23 得分 15
class action
{
public:
int in_delete;
char value;
int pos;
action(int one,char two,int three):in_delete(one),value(two),pos(three){};
};
int have(char *p,char const *q)
{
int i=-1;
while(*q!='\0'&&*p!='\0')
{
if(*q==*p)
{
return ++i;
}
else
{
p++;
i++;
}
}
if(*p=='\0')
{
return -1;
}
return i;
}
void main()
{
queue<action*> col;
char s[]="abcdesdasd",d[]="acd2efdsadsad";
char *p=s,*q=d;
int status=0;
while(*q!='\0')
{
status=have(p,q);
if(status==0)
{
p++;
q++;
}
else if(status==-1)
{
col.push((new action(-1,*q,p-s+1))); /* insert *q */
q++;
}
else
{
col.push((new action(1,*p,p-s+1))); /* delete *p */
p++;
}
}
action* display;
while(!col.empty())
{
display=col.front();
col.pop();
if(display->in_delete==-1)
{
cout<<"insert";
}
else
{
cout<<"delete";
}
cout<<":"<<display->value<<":"<<display->pos<<endl;
}
cout<<"successed"<<endl;
}Top
14 楼nipcdll（）回复于 2006-03-20 15:52:18 得分 5
http://www.codeproject.com/string/SimilarStrings.aspTop
15 楼turbocamel（骆驼◎沙漠.com）回复于 2006-03-20 17:18:54 得分 8
http://sourceforge.net/project/showfiles.php?group_id=13216
这是winMerge的源代码下在地址，一个很好用的文本比较工具，而且是OpenSource的
Top
16 楼mademelaugh（五朝臣子(以接分为荣，以不结帖为耻)）回复于 2006-03-20 18:20:09 得分 0
谢谢各位！Top
相关问题
关键词
得分解答快速导航
相关链接
广告也精彩
反馈
