//	This source and similar text sequences method apply to GNU General Public License. 
//			Copyright (C) 2001-2012 , 2015 Jasenko Dzinleski 

//		This program is free software; you can redistribute it
//	and/or modify it under the terms of the GNU General Public License as
//	published by the Free Software Foundation; either version 2 of the
//	License, or (at your option) any later version. 

//	This program is distributed in the hope that it will be useful, but
//	WITHOUT ANY WARRANTY; without even the implied warranty of
//	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
//	General Public License for more details. 

//	You should have received a copy of the GNU General Public License along
//	with this program; if not, write to the Free Software Foundation, Inc.,
//	51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.

//  	Similar Text Sequences (64-bit)		
//	written by Dzinleski Jasenko  December 2012 , 2015 , April 2017

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

FILE	*f1,*f2;

char		infn[256]="fasta__.txt";
char		outfn[256]="out_.txt";

long		bab[100000][3][9];	int babi=0;
int		fb_[1024];int fbi=0;

int 		cv[256];int cvi=0;
char		nl[256];int nli=0;
int		nc=0;

long long	b64o,b64e;
long 		d1,d2,d3;
long 		d1_,d2_,d3_;

long 		dc1,dc2,dc3;
long 		dc1_,dc2_,dc3_;

long 		dd1,dd2,dd3;
long 		dd1_,dd2_,dd3_;
int		df=0;

char		sv[256];
char		sva[1024][256];int svai=0;
char		svl[256];
char		svl_[1024];

//--------------------------------------------------------------
	#include 	<unistd.h>
	#include 	<wait.h>

	int p_1_(char *ar[],char ofn[256])
	{
		int 	outf[2];
		int	status;
		pipe(outf);pid_t pid=fork();if(pid==0){while((status=execvp(ar[0],ar))<0){while(wait(&status)!= pid);}}
		return(0);
	}
//--------------------------------------------------------------

int p_1(char infn_[256],char outfn_[256])
{

int	a,b,c,d,cL,h;
int	i,j,k,l,m,n;
int	fb;

char 	cv[256];
char 	cs[100][256];int csi=0;int csj=0;

	f1=fopen(infn_,"rb");
	f2=fopen(outfn_,"w");
	fb=getc(f1);
	for(i=0;i<256;++i){cv[i]='\0';}a=0;while((fb!=10)&&(fb!=13)&&!feof(f1)){cv[a]=fb;++a;fb=getc(f1);}while((fb==10)||(fb==13)&&!feof(f1)){fb=getc(f1);}
	for(i=0;i<100;++i){for(j=0;j<256;++j){cs[i][j]='\0';}}csi=0;csj=0;for(i=0;i<strlen(cv);++i){cs[0][csj]=cv[i];++csj;}
	while(!feof(f1))
	{
		for(i=0;i<256;++i){cv[i]='\0';}a=0;while((fb!=10)&&(fb!=13)&&!feof(f1)){cv[a]=fb;++a;fb=getc(f1);}
		while((fb==10)||(fb==13)&&!feof(f1)){fb=getc(f1);}

		++csi;csj=csi;for(i=0;i<csi;++i){cs[csi][i]=' ';}for(i=0;i<strlen(cv);++i){cs[csi][csj]=cv[i];++csj;}
		b=csi;c=strlen(cs[csi]);d=0;while(b<c){if(cs[-1+csi][b]==cs[csi][b]){++d;};++b;}//printf("!%d %d!\n",d,strlen(cs[csi]));

		if(d==-2+strlen(cs[csi]))
		{
			while(d==-2+strlen(cs[csi])&&!feof(f1))
			{
				for(i=0;i<256;++i){cv[i]='\0';}a=0;while((fb!=10)&&(fb!=13)&&!feof(f1)){cv[a]=fb;++a;fb=getc(f1);}
				while((fb==10)||(fb==13)&&!feof(f1)){fb=getc(f1);}
				++csi;csj=csi;for(i=0;i<csi;++i){cs[csi][i]=' ';}for(i=0;i<strlen(cv);++i){cs[csi][csj]=cv[i];++csj;}
				b=csi;c=strlen(cs[csi]);d=0;while(b<c){if(cs[-1+csi][b]==cs[csi][b]){++d;};++b;}
			}
			i=0;while(i<strlen(cs[0])){fprintf(f2,"%c",cs[0][i]);++i;}
			j=-1+strlen(cs[0]);i=csi;while(j<strlen(cs[i])){fprintf(f2,"%c",cs[i][j]);++j;}
			fprintf(f2,"\n");
		}
		for(i=0;i<100;++i){for(j=0;j<256;++j){cs[i][j]='\0';}}csi=0;csj=0;for(i=0;i<strlen(cv);++i){cs[0][csj]=cv[i];++csj;}

	}
	fclose(f1);
	fclose(f2);

	return(0);
	
}

int p_2(char infn_[256],char outfn_[256])
{
	int 	i,j,k,fbyte;
	int	cc=0;
	char	sb[2][256];

	for(i=0;i<256;++i){sb[0][i]='\0';sb[1][i]='\0';}
	f1=fopen(infn_,"rb");if(f1==NULL){return(0);} 
	f2=fopen(outfn_,"w");
	fbyte=getc(f1);j=0;while(!feof(f1)&&fbyte!=13&&fbyte!=10){sb[0][j]=fbyte;++j;fbyte=getc(f1);}
	while(!feof(f1)&&(fbyte==13||fbyte==10)){fbyte=getc(f1);}
	while(!feof(f1))
	{
		j=0;k=0;while(!feof(f1)&&fbyte!=13&&fbyte!=10){sb[1][j]=fbyte;if(sb[0][j]==sb[1][j]){++k;}++j;fbyte=getc(f1);}
		if(strlen(sb[0])!=k){++cc;fprintf(f2,"%03d\t%s\n",cc,sb[0]);for(i=0;i<256;++i){sb[0][i]='\0';}for(i=0;i<strlen(sb[1]);++i){sb[0][i]=sb[1][i];}cc=0;}else{++cc;}
		while(!feof(f1)&&(fbyte==13||fbyte==10)){fbyte=getc(f1);}for(i=0;i<256;++i){sb[1][i]='\0';}
	}
	fclose(f1);
	fclose(f2);
	//
	return(0);
}

int bp___(long long b1,long long b2,long long b3)
{
	
	d1=(long)((((b1&b64e)>>1)^(b2&b64o))|((b1&b64e)^((b2&b64o)<<1)));	
	d2=(long)((((b1&b64e)>>1)^(b3&b64o))|((b1&b64e)^((b3&b64o)<<1)));
  //d3=(long)((((d1&b64e)>>1)^(d2&b64o))|((d1&b64e)^((d2&b64o)<<1)));

	d1_=(long)((((b2&b64e)>>1)^(b1&b64o))|((b2&b64e)^((b1&b64o)<<1)));	
	d2_=(long)((((b2&b64e)>>1)^(b3&b64o))|((b2&b64e)^((b3&b64o)<<1)));
  //d3_=(long)((((d2_&b64e)>>1)^(d1_&b64o))|((d2_&b64e)^((d1_&b64o)<<1)));
	
	return(0);
}

int main(int argc,char *argv[])
{

	int	a,b,c,d=0,e,fb;
	int	i,j,k,l,m;
	int	fbyte;
	int	lc=0;
	char 	cs1[256];
	char 	cs2[256];
		
	int	b1_,b2_,b3_,b4_,b5_;
	int	b6_,b7_,b8_,b9_,b10_;
	int	b11_,b12_,b13_,b14_,b15_;
	int	b16_,b17_,b18_;
	
	long long	b1,b2,b3;

	b64o=0;for(i=0;i<64;i+=2){b64o|=1<<i;}
	b64e=0;for(i=1;i<64;i+=2){b64e|=1<<i;}		

	f1=fopen(infn,"rb");
	f2=fopen(outfn,"wb");

    	for(i=0;i<256;++i){cv[i]='\0';}
    	for(i=0;i<18;++i){fbyte=getc(f1);if(fbyte==13||fbyte==10){while((fbyte==13||fbyte==10)&&!feof(f1)){fbyte=getc(f1);}++lc;}cv[i]=fbyte;}
	
	while(!feof(f1))
	{

        	b1_=cv[0];
        	b2_=cv[1];
        	b3_=cv[2];
        	b4_=cv[3];
        	b5_=cv[4];
        	b6_=cv[5];
        	b7_=cv[6];
        	b8_=cv[7];
        	b9_=cv[8];
        	b10_=cv[9];
        	b11_=cv[10];
        	b12_=cv[11];
        	b13_=cv[12];
        	b14_=cv[13];
        	b15_=cv[14];
        	b16_=cv[15];
        	b17_=cv[16];
        	b18_=cv[17];

		b1=((b1_<<56-1)|(b3_<<48-1)|(b5_<<40-1)|(b7_<<32-1)|(b9_<<24-1)|(b11_<<16-1)|(b13_<<8-1)|(b15_<<0));
		b2=((b2_<<56-1)|(b4_<<48-1)|(b6_<<40-1)|(b8_<<32-1)|(b10_<<24-1)|(b12_<<16-1)|(b14_<<8-1)|(b16_<<0));
		b3=((b3_<<56-1)|(b5_<<48-1)|(b7_<<40-1)|(b9_<<32-1)|(b11_<<24-1)|(b13_<<16-1)|(b15_<<8-1)|(b17_<<0));
		b1=b1<<1;b2=b2<<1;b3=b3<<1;
		bp___(b1,b2,b3);
		
		dc1=d1;
		dc2=d2;
		dc3=d3;
		dc1_=d1_;
		dc2_=d2_;
		dc3_=d3_;

	    	b1=((b2_<<56-1)|(b4_<<48-1)|(b6_<<40-1)|(b8_<<32-1)|(b10_<<24-1)|(b12_<<16-1)|(b14_<<8-1)|(b16_<<0));
	    	b2=((b3_<<56-1)|(b5_<<48-1)|(b7_<<40-1)|(b9_<<32-1)|(b11_<<24-1)|(b13_<<16-1)|(b15_<<8-1)|(b17_<<0));
	  	b3=((b4_<<56-1)|(b6_<<48-1)|(b8_<<40-1)|(b10_<<32-1)|(b12_<<24-1)|(b14_<<16-1)|(b16_<<8-1)|(b18_<<0));
		b1=b1<<1;b2=b2<<1;b3=b3<<1;
		bp___(b1,b2,b3);
		
		dd1=d1;
		dd2=d2;
		dd3=d3;
		dd1_=d1_;
		dd2_=d2_;
		dd3_=d3_;		

		if(babi==0)
		{
			
			bab[babi][0][0]=dc1;
			bab[babi][0][1]=dc2;
			bab[babi][0][2]=dc1_;
			bab[babi][0][3]=dc2_;
					
			bab[babi][1][0]=dd1;
			bab[babi][1][1]=dd2;
			bab[babi][1][2]=dd1_;
			bab[babi][1][3]=dd2_;
			
			bab[babi][2][0]=(b1_<<8)|b2_;
			bab[babi][2][1]=(b3_<<8)|b4_;
			bab[babi][2][2]=(b5_<<8)|b6_;
			bab[babi][2][3]=(b7_<<8)|b8_;
			bab[babi][2][4]=(b9_<<8)|b10_;
			bab[babi][2][5]=(b11_<<8)|b12_;
			bab[babi][2][6]=(b13_<<8)|b14_;
			bab[babi][2][7]=(b15_<<8)|b16_;
			bab[babi][2][8]=(b17_<<8)|b18_;
			
			++babi;if(babi==100000){return(0);}
										
		}else{
			
			c=-1;
			for(i=0;i<babi;++i)
			{
				j=0;k=0;
				
				if(bab[i][0][0]==dc1 ){++j;}
				if(bab[i][0][1]==dc2 ){++j;}
				if(bab[i][0][2]==dc1_){++j;}
				if(bab[i][0][3]==dc2_){++j;}
				
				if(bab[i][1][0]==dd1 ){++k;}
				if(bab[i][1][1]==dd2 ){++k;}
				if(bab[i][1][2]==dd1_){++k;}
				if(bab[i][1][3]==dd2_){++k;}
				
				if(j>=1&&k>=1)
				{
					if(c==-1){c=j+k;e=i;}else{if(c<(j+k)){c=j+k;e=i;}}
				}
			}
			
			if(c!=-1)
			{
								
				j=0;k=0;
				if(bab[e][0][0]==dc1 ){++j;}
				if(bab[e][0][1]==dc2 ){++j;}
				if(bab[e][0][2]==dc1_){++j;}
				if(bab[e][0][3]==dc2_){++j;}
				
				if(bab[e][1][0]==dd1 ){++k;}
				if(bab[e][1][1]==dd2 ){++k;}
				if(bab[e][1][2]==dd1_){++k;}
				if(bab[e][1][3]==dd2_){++k;}
				
				if(j>=2&&k>=2)
				{
					for(l=0;l<256;++l){cs1[l]='\0';}l=0;
					cs1[l]=b1_;++l;
					cs1[l]=b2_;++l;
					cs1[l]=b3_;++l;
					cs1[l]=b4_;++l;
					cs1[l]=b5_;++l;
					cs1[l]=b6_;++l;
					cs1[l]=b7_;++l;
					cs1[l]=b8_;++l;
					cs1[l]=b9_;++l;
					cs1[l]=b10_;++l;
					cs1[l]=b11_;++l;
					cs1[l]=b12_;++l;
					cs1[l]=b13_;++l;
					cs1[l]=b14_;++l;
					cs1[l]=b15_;++l;
					cs1[l]=b16_;++l;
					cs1[l]=b17_;++l;
					cs1[l]=b18_;++l;
					for(l=0;l<256;++l){cs2[l]='\0';}l=0;
					cs2[l]=(bab[e][2][0]&0xff00)>>8;++l;
					cs2[l]=(bab[e][2][0]&0x00ff)>>0;++l;
					cs2[l]=(bab[e][2][1]&0xff00)>>8;++l;
					cs2[l]=(bab[e][2][1]&0x00ff)>>0;++l;
					cs2[l]=(bab[e][2][2]&0xff00)>>8;++l;
					cs2[l]=(bab[e][2][2]&0x00ff)>>0;++l;
					cs2[l]=(bab[e][2][3]&0xff00)>>8;++l;
					cs2[l]=(bab[e][2][3]&0x00ff)>>0;++l;
					cs2[l]=(bab[e][2][4]&0xff00)>>8;++l;
					cs2[l]=(bab[e][2][4]&0x00ff)>>0;++l;
					cs2[l]=(bab[e][2][5]&0xff00)>>8;++l;
					cs2[l]=(bab[e][2][5]&0x00ff)>>0;++l;
					cs2[l]=(bab[e][2][6]&0xff00)>>8;++l;
					cs2[l]=(bab[e][2][6]&0x00ff)>>0;++l;
					cs2[l]=(bab[e][2][7]&0xff00)>>8;++l;
					cs2[l]=(bab[e][2][7]&0x00ff)>>0;++l;
					cs2[l]=(bab[e][2][8]&0xff00)>>8;++l;
					cs2[l]=(bab[e][2][8]&0x00ff)>>0;++l;
                   
					if(df){for(l=0;l<strlen(cs1);++l){printf("%c",cs1[l]);}printf("\n");}
					for(l=0;l<strlen(cs1);++l)
					{
						if(cs1[l]==cs2[l])
						{
							if(df){printf("|");}
							fb_[fbi]=cs1[l];++fbi;if(fbi>=1024){fbi=0;}
						}else{
							if(df){printf("_");}
						}
					}
					//printf("\n");
					if(df){for(l=0;l<strlen(cs2);++l){printf("%c",cs2[l]);}printf("\n");}
					for(l=0;l<strlen(cs1);++l){if(cs1[l]==cs2[l]){fprintf(f2,"%c",cs1[l]);}else{fprintf(f2,"_");}}
					fprintf(f2,"%c%c",13,10);
						
					//printf("%d\t%d\t%d\t%d\n\n",j,k,e,lc);
					++d;
				}
				
			}else{
					
				bab[babi][0][0]=dc1;
				bab[babi][0][1]=dc2;
				bab[babi][0][2]=dc1_;
				bab[babi][0][3]=dc2_;
					
				bab[babi][1][0]=dd1;
				bab[babi][1][1]=dd2;
				bab[babi][1][2]=dd1_;
				bab[babi][1][3]=dd2_;
			
				bab[babi][2][0]=(b1_<<8)|b2_;
				bab[babi][2][1]=(b3_<<8)|b4_;
				bab[babi][2][2]=(b5_<<8)|b6_;
				bab[babi][2][3]=(b7_<<8)|b8_;
				bab[babi][2][4]=(b9_<<8)|b10_;
				bab[babi][2][5]=(b11_<<8)|b12_;
				bab[babi][2][6]=(b13_<<8)|b14_;
				bab[babi][2][7]=(b15_<<8)|b16_;
				bab[babi][2][8]=(b17_<<8)|b18_;

				++babi;if(babi==100000){return(0);}
				
			}	
		}

        	j=0;for(i=1;i<18;++i){cv[j]=cv[i];++j;}
        	fbyte=getc(f1);if(fbyte==13||fbyte==10){while((fbyte==13||fbyte==10)&&!feof(f1)){fbyte=getc(f1);}++lc;}cv[--i]=fbyte;

	}
	fclose(f1);
	fclose(f2);
	//printf("%d\t%d\n",babi,d);

	p_1("out_.txt","tout_.txt");
	char *cm[]={"sort","tout_.txt","-ostout_.txt",NULL};p_1_(cm,"out.txt");
	p_2("stout_.txt","cstout_.txt");
	char *cm_[]={"sort","cstout_.txt","-oscstout_.txt",NULL};p_1_(cm_,"out.txt");

	return(0);

}