Diff lcs

In computing, diffis a file comparison utility that outputs the differences between twofiles. It is typically used to show the changes between a file and a formerversion of the same file. Diff displays the changes made per line for textfiles.

The operation of diffis based on solving the longest common subsequence problem which is asfollows: Given two sequences A = a1, a2, …, aM, and B =b1, b2, …, bN, find the length, k, of the longestsequence C = c1, c2, …, ck such thatC is a subsequence of both A and B. As an example, if

A = d, y, n, a, m,i, c

and

B = p, r, o, g, r,a, m, m, i, n, g

then the longest common subsequence is a, m, i andhas length 3.

From the longestcommon subsequence it's only a small step to get diff-like output:

dyn-progr+m+c-ng+

where “–” means a deletionfrom and “+” means an addition to the first string.

Now you are supposed to simulate the diff operation.

InputSpecification:

Your program must read test cases from a file “input.txt”.The input file consists of several test cases. Each case contains the contentsof two files. The case starts with two non-negative integers N and M (both 50), then followed by N+M lines, each contains a string of nomore than 80 characters. The first N lines are the contents of the firstfile, while the second M lines are of the second file.

The input is finished by a negative N.

OutputSpecification:

For each test case, you aresupposed to print to a file “output. txt”. If there is no difference found between the two files, print in aline “No differencefound”. If there is nothing incommon between the two files, print in a line “Totally different”. Otherwise, first print in a line the length of thelongest sequence. Then for each line of the first file, print the line number,and output the differences in the diff-like format line by line, as shown bythe sample output.

Sample Input:

1 1

This is a test

This is a test

1 1

ab

cd

1 1

dynamic

programming

4 4

This is a test

which ismore complicated                                 

zzz

than ...

This is another test

of the project

which is much morecomplex

than the previous one

-100

Sample Output:

No difference found

Totally different

3

line #1:

dyn-progr+m+c-ng+

39

line #1:

nother+                              

line #2:

of the project+

much+icat-d-

line #3:

zzz-

line #4:

x+

...-the previous one+

#include<iostream>
#include<fstream>
#include<string>
#include<sstream>
using namespace std;
const int SIZE=10000;
const char nextLineA='&';
const char nextLineB='&';
int c[SIZE][SIZE];
int route[SIZE][2];
ofstream out("output.txt");
ifstream in("input.txt");
//找出二整数之间最大数 
int Max(int x, int y){
	return x > y ? x : y;
}
//找出最长子序列的长度,并将结果记录在c[][]中 
void LCSLength(string x, string y, int c[][SIZE]){//最终c[x.size()][y.size()]中存储的是最厂子序列的值 
	for(int i=0;i<=x.size();++i) c[0][i]=0;
	for(int i=0;i<=y.size();++i) c[i][0]=0;
	for(int i=1;i<=x.size();++i)
		for(int j=1;j<=y.size();++j)
			c[i][j]=  x[i-1]==y[j-1] ? c[i-1][j-1]+1 : Max(c[i-1][j],c[i][j-1]);
}
//找出最长子序列路径,其中route[][0]记录第一个序列中的位置,route[][1]记录第二个序列中的位置 
void FindLCS(int c[][SIZE], int route[][2], int xLen, int yLen){
	int length=c[xLen][yLen];
	while(length--){
		while(c[xLen-1][yLen]!=c[xLen][yLen-1] || c[xLen][yLen]!=c[xLen-1][yLen-1]+1)
			c[xLen][yLen]==c[xLen][yLen-1] ? --yLen : --xLen ;
		route[length][0]=--xLen;//相同元素在x中的位置 
		route[length][1]=--yLen;//相同元素在y中的位置
	}
}
/**************************
*length : LCS的长度       *
*out : 用于文件输出的对象 *
***************************/
void Diff(string x, string y, int route[][2], int length){
	int xi,yi;//用于记录两个相同字符间不相同的字符 
	xi=yi=-1;
	int line=1;
	out<<"line #"<<line++<<":"<<endl;
	for(int i=0;i<length;++i){
		int _xi=xi;
		int _yi=yi; 
		while(xi<route[i][0]) ++xi;
		while(yi<route[i][1]) ++yi;
		if(1==xi-_xi && 1!=yi-_yi){
			for(int k=_yi+1;k<yi;++k)
				out<<y[k];
			out<<"+";
		}
		else if(1!=(xi-_xi) && 1!=(yi-_yi)){
			for(int k=_xi+1;k<xi;++k)
				out<<x[k];
			out<<"-";
			for(int k=_yi+1;k<yi;++k)
				out<<y[k];
			out<<"+";
		}
		else if(1!=xi-_xi && 1==yi-_yi){
			for(int k=_xi+1;k<xi;++k)
				out<<x[k];
			out<<"-";
		}
		if(x[xi]==nextLineA && xi!=route[length-1][0]) out<<endl<<"line #"<<line++<<":"<<endl;
	}
	out<<endl;
}
int main(){
	int m,n;
	while(in>>m>>n , m > 0){
		string str1="",str2="",_str1,_str2;
		getline(in,_str1);//去掉换行
		for(int i=0;i<m;++i){
			getline(in,_str1);
			str1+=_str1;
			str1+=nextLineA;
		}
		for(int i=0;i<n;++i){
			getline(in,_str2);
			str2+=_str2;
			str2+=nextLineB;
		}
		LCSLength(str1,str2,c);
		FindLCS(c, route, str1.size(), str2.size());
		out<<c[str1.size()][str2.size()]<<endl;
		if(c[str1.size()][str2.size()]==str1.size() && c[str1.size()][str2.size()]==str2.size())
			out<<"No difference found"<<endl;
		else if( m==n && m==c[str1.size()][str2.size()])
			out<<"Toatally different"<<endl;
		else Diff(str1, str2, route,c[str1.size()][str2.size()]); 
	}
	return 0;
}