#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)
	{
		replace(A,x,maxmatch,La);
		replace(B,y,maxmatch,Lb);
		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);
}

status replace(SString s,int pos,int len,int Ls) //用空格来代替两个token串中的最大匹配子串
{
	int i;
	if(pos<1||pos>Ls-len+1||len<0)
	return 0;
	s[pos]=' ';
	for(i=pos+len;i<=Ls;i++)
	{
		s[i-len+1]=s[i];
	}
	return 1;
}

int copy(float n) //此函数判断是否抄袭
{
	printf("\n相似度超过0.8，则认为是抄袭");
	if(n>=0.8)
	printf("\n这两个代码有抄袭嫌疑，请做进一步检查");
	else
	printf("\n这两个代码没有抄袭嫌疑");
	return 0;
}

int main(void)
{
	system("cls"); //清屏
	char name1[50];
	char name2[50]; //存储输入的文件路径字符串
	FILE *f1,*f2;
	system("color F3");
	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;
}