#include <stdio.h> 
#include <string.h> 
#include <ctype.h> 
#include <conio.h> 
#include <malloc.h> 
#include <stdlib.h> 
#include <windows.h> 
#define N 10000 
#define M 10000
#define MAXSTRLEN 10000 //定义最大串长

typedef int status;
typedef char SString[MAXSTRLEN+1]; //串的定长顺序存储表示 

SString a[3]={"int","long","short"};
SString b[2]={"float","double"};
SString c[15]={"&&","||","++","--","+","-","*","/","=",">=","<=","==","!=",">","<"};
SString d[12]={"[","]","{","}","(",")",",",";","'","#",";","."}; 
SString e[29]={"auto","break","case","char","const","continue","default","do","else","enum",
"extern","for","goto","if","main","printf","register","return","signed","sizeof",
"static","struct","switch","typedef","union","unsigned","void","while","volatile"};

char type(char *str);
void token(char name[],char list[],char token[],FILE *table);
void simple(int MinMatchLen,FILE *fp1,FILE *fp2);
status replace(SString s,int pos,int len,int Ls);
int copy(float n);



char type(char *str) //确定串的类型 
{
	int i;
	for(i=0;i<3;i++) //整型 
	{
		if(strcmp(str,a[i])==0)
		return 'K';
	}
	for(i=0;i<2;i++) //浮点型
	{
		if(strcmp(str,b[i])==0)
		return 'E';
	}
	for(i=0;i<15;i++) //运算符
	{
		if(strcmp(str,c[i])==0)
		return 'A';
	}
	for(i=0;i<12;i++) //分界符 
	{
		if(strcmp(str,d[i])==0)
		return 'R';
	}
	for(i=0;i<29;i++) //标识符和关键字 
	{
		if(strcmp(str,e[i])==0)
		return 'Y';
	}
	if(isdigit(str[0])) //数字0－9
	{
		return 'N';
	}
	if(!isalnum(str[0])) //汉字 
	{
		return 'H';
	} 
	else return 'C';//一般的变量与字符
}

void token(char name[],char list[],char token[],FILE *table) //将文件中的字符串分别切割转换为token串
{
	FILE *in,*out;
	char ch,c,buffer[N],*link[M];
	int i=0,j=0,k=0,LenLink=0;
	if((in=fopen(name,"r+"))==NULL)
	{
		printf("源文件无法打开！\n");
		exit(0);
	}
	if((out=fopen(list,"w+"))==NULL)
	{
		printf("文件写入失败！\n");
		exit(0);
	}
	if((table=fopen(token,"w+"))==NULL)
	{
		printf("文件写入失败！\n");
		exit(0);
	}
	while(!feof(in)) //逐字读取文件
	{
		ch=fgetc(in);
		if(ch=='\t' || ch==' ' || ch== '\n') continue;//去掉制表符、空格、回车 
		if(isalpha(ch)) //如果首字符是字母
		{
			while(isalnum(ch)&&(i<N)) //其他位是字母或数字
			{
				buffer[i++]=ch;
				ch=fgetc(in);
			}
			buffer[i]='\0';//串尾 
			link[j++]=(char *)malloc(sizeof(char)*(strlen(buffer)+1));
			strcpy(link[j-1],buffer);
			i=0;
			fseek(in,-1L,1); //在文件当中定位，回到前一字节处 
		}

		else if(isdigit(ch)) //如果首字符是数字
		{
			while(isalnum(ch)&&(i<N)) //其他位是字母或数字
			{
				buffer[i++]=ch;
				ch=fgetc(in);
			}
			buffer[i]='\0';
			link[j++]=(char *)malloc(sizeof(char)*(strlen(buffer)+1));
			strcpy(link[j-1],buffer);
			i=0;
			fseek(in,-1L,1);
		}

		else if(!isalnum(ch)) //如果首字符既不是数字也不是字母 
		{
			if(ch!='\n'&&ch!=' '&&ch!='\t')//不是换行、空格或制表 
			{
				if(ch=='>'||ch=='<'||ch=='!')//>=,<=,!=这些需被认为是一个符号
				{
					if((c=fgetc(in))=='=')
					{
						buffer[i++]=ch;
						buffer[i++]=c;
						buffer[i]='\0';
						link[j++]=(char *)malloc(sizeof(char)*3); strcpy(link[j-1],buffer);
						i=0;
					}
					else
					{
						buffer[i++]=ch;
						buffer[i]='\0';
						link[j++]=(char *)malloc(sizeof(char)*2); 
						strcpy(link[j-1],buffer);
						i=0;
						fseek(in,-1L,1);
					}
				}

				else if(ch=='+'||ch=='-'||ch=='&'||ch=='|'||ch=='=')//++,--,&&,||,==这些需被认为是一个符号
				{
					if((c=fgetc(in))==ch) 
					{
						buffer[i++]=ch;
						buffer[i++]=c;
						buffer[i]='\0';
						link[j++]=(char *)malloc(sizeof(char)*3); 
						strcpy(link[j-1],buffer);
						i=0;
					}
					else
					{
						buffer[i++]=ch;
						buffer[i]='\0';
						link[j++]=(char *)malloc(sizeof(char)*2); strcpy(link[j-1],buffer);
						i=0;
						fseek(in,-1L,1);
					}
				}

				else //其他符号
				{
					buffer[i++]=ch;
					buffer[i]='\0';
					link[j++]=(char *)malloc(sizeof(char)*2); 
					strcpy(link[j-1],buffer);
					i=0;
				}
			}
		}
	} 
		LenLink = j-1; //存到link中的总长度
		for(i=0;i<LenLink;i++) //打印token中的内容
		{
			c=type(link[i]);
			if(c=='N'||c=='A'||c=='R')//数字，符号在表中保留
				fputs(link[i],table);
			if(c=='C') //变量均替换为id
				fputs("id",table);
			if(c=='K')//关键字int,short,long替换为zh
				fputs("zh",table);
			if(c=='E')//关键字float,double替换为fu
				fputs("fu",table);
			if(c=='Y')//其他关键字不变
				fputs(link[i],table);
			if(c=='H')//汉字删掉
				fputs("\0",table);
		}
		fclose(table);
		fprintf(out,"\t***** 单词类型观察表 *****\n");//打印list中的内容
		fprintf(out,"\t K --int,short,long \n");
		fprintf(out,"\t E --float,double\n");
		fprintf(out,"\t Y --其他关键字\n");
		fprintf(out,"\t A --运算符号\n");
		fprintf(out,"\t R --语言符号\n");
		fprintf(out,"\t N --数字\n");
		fprintf(out,"\t H --汉字\n");
		fprintf(out,"\t C --一般变量或标识符\n");
		fprintf(out,"\t*****************************\n");
		
		for(i=0;i<LenLink;i++)
		{
			c=type(link[i]); //判断单词的类型
			fputc('(',out);
			fputc(c,out);
			fputc(',',out);
			fputs(link[i],out);
			fputc(',',out);
			fprintf(out,"%d",i);
			fputc(')',out);
			fputc('\n',out);
		}
	
} 
void simple(int MinMatchLen,FILE *fp1,FILE *fp2)//计算相似度，MinMatchLen: 公共子串要达到的最小长度
{
	SString A,B;
	char ch,h;
	int i=0,j=0,k,t,s,a=1,La,Lb,lena,lenb,x,y;
	float n;
	int MatchLen=0;//所有公共子串的总长度
	int maxmatch;//当前最大公共子串长度
	if ((fp1=fopen("token1.txt","r"))==NULL)//设定文件位于当前目录下
	{
		printf("文件打开失败！");
		getch();
		exit(0);
	}
	A[++i]=fgetc(fp1);
	while(!feof(fp1))
		A[++i]=fgetc(fp1);
	fclose(fp1);
	La=i-1;
	printf("token串1长度为%d，",La);
	if ((fp2=fopen("token2.txt","r"))==NULL)//设定文件位于当前目录下
	{
		printf("文件打开失败！");
		getch();
		exit(0);
	}
	B[++j]=fgetc(fp2);
	while(!feof(fp2))
	B[++j]=fgetc(fp2);
	fclose(fp2);
	Lb=j-1;
	printf("token串2长度为%d\n",Lb);
	printf("是否要查看这两个token串？Y/N ");
	h=getchar();
	if(h=='Y'||h=='y')
	{
		ShellExecute(NULL,"open","token1.txt",NULL,NULL,SW_SHOWNORMAL);
		ShellExecute(NULL,"open","token2.txt",NULL,NULL,SW_SHOWNORMAL);
	}
	getchar();
	printf("\n将超过指定长度的公共子串用空格替换，是否要查看细节？Y/N ");
	ch=getchar();
	lena=i-1;
	lenb=j-1;
	do{
		maxmatch=MinMatchLen;
		for(i=1;i<=La;i++)
		{
			for(j=1;j<=Lb;j++)
			{
				k=0;
				while((k<=La-i)&&(k<=Lb-j)&&(A[i+k]==B[j+k])&&((A[i+k]!='\0')||(B[j+k]!='\0'))&&(A[i+k]!=' ')&&(B[j+k]!=' '))//串A的第i+k个字符与串B的第j+k个字符是否相等 
					k++;
				if(k>maxmatch)
				{
					maxmatch=k;
					x=i;
					y=j;
				}
			}
		}
		if(maxmatch>MinMatchLen)
		{
			{
				int i;
				if(x<1||x>La-maxmatch+1||maxmatch<0)
				break;
				A[x]=' ';
				for(i=x+maxmatch;i<=La;i++)
				{
					A[i-maxmatch+1]=A[i];
				}
			}
			{
				int i;
				if(y<1||y>Lb-maxmatch+1||maxmatch<0)
				break;
				B[y]=' ';
				for(i=y+maxmatch;i<=Lb;i++)
				{
					B[i-maxmatch+1]=B[i];
				}
			}			
						
			La=La-maxmatch+1;
			Lb=Lb-maxmatch+1;
			MatchLen+=maxmatch;
		}
		if(ch=='Y'||ch=='y')
		{
			printf("第%d次检查两串中的匹配串\n",a);
			a++;
			for(s=1;s<=La;s++)
				printf("%c",A[s]);
			printf("\n");
			for(s=1;s<=Lb;s++)
				printf("%c",B[s]);
			printf("\n");
		}
	}while(maxmatch>MinMatchLen);

//	printf("\n已经没有能够匹配的公共子串了\n");
	n=(2.0*MatchLen)/(lena+lenb);
	printf("公共子串的总长为%d,",MatchLen);
	printf("根据公式\n");
	printf("\t\t——————————————————————————\n");
	printf("\t\t| 相似度=(2×公共子串长度)÷(串A长度+串B长度) |\n");
	printf("\t\t——————————————————————————\n");
	printf("这两串代码的相似度为%f\n",n);
	copy(n);
}

int copy(float n) //此函数判断是否抄袭
{
	if(n>=0.8)
	printf("\n相似度超过0.8,这两个代码有抄袭嫌疑");
	else
	printf("\n相似度未超过0.8,这两个代码没有抄袭嫌疑");
	return 0;
}

int main(void)
{
	system("cls");
	FILE *f1,*f2;
	printf("请把两个文件分别命名为 \"file1.c\" 和 \"file2.c\",放到此程序的目录下，再回到此程序按下回车\n");
	getchar();
	token("file1.c","list1.txt","token1.txt",f1);
	token("file2.c","list2.txt","token2.txt",f2); 
	printf("\ntoken串已生成成功");
	getchar();
	simple(3,f1,f2);
	return 0;
}