Compare text

Find the difference between two text files

Real-time diff

Unified diff

Collapse lines

Highlight change

Syntax highlighting

Tools

Diffchecker Desktop The most secure way to run Diffchecker. Get the Diffchecker Desktop app: your diffs never leave your computer!Get Desktop

Comparing sensitive data, confidential files or internal emails?

Most legal and privacy policies prohibit uploading sensitive data online. Diffchecker Desktop ensures your confidential information never leaves your computer. Work offline and compare documents securely.

Download Diffchecker Desktop Learn more

Untitled diff

Created 9 years agoDiff never expires

2 removals

206 lines

2 additions

206 lines

//#pragma comment(linker, "/STACK:16777216")

#include <fstream>

#include <iostream>

#include <string>

#include <complex>

#include <math.h>

#include <set>

#include <vector>

#include <map>

#include <queue>

#include <stdio.h>

#include <stack>

#include <algorithm>

#include <list>

#include <ctime>

#include <memory.h>

#include <ctime>

#include <assert.h>

#define y0 sdkfaslhagaklsldk

#define y1 aasdfasdfasdf

#define yn askfhwqriuperikldjk

#define j1 assdgsdgasghsf

#define tm sdfjahlfasfh

#define lr asgasgash

#define eps 1e-8

#define M_PI 3.141592653589793

#define bs 1000000007

#define bsize 512

using namespace std;

int tests;

long long pw[1<<24];

int n;

string st;

map<long long, int> F;

string word[1<<24];

map<long long, int> revs;

long long s[1<<24],s2[1<<24];

long long gh(string&st)

{

long long s=0;

for (int i=0;i<st.size();i++)

s=s*173+st[i];

return s;

}

bool pal(int l,int r)

{

long long S1=s[r]-s[l-1];

long long S2=s2[l]*pw[l-1];

return (S1==S2);

}

int main(){

//freopen("beavers.in","r",stdin);

//freopen("beavers.out","w",stdout);

//freopen("F:/in.txt","r",stdin);

//freopen("F:/output.txt","w",stdout);

ios_base::sync_with_stdio(0);

//cin.tie(0);

cin>>tests;

pw[0]=1;

for (int i=1;i<=10000000;i++)

pw[i]=pw[i-1]*173;

for (;tests;--tests)

{

cin>>n;

if (n>1000000)

return 1;

getline(cin,st);

F.clear();

long long ans=0;

int emp=0;

for (int i=1;i<=n;i++)

{

//cin>>word[i];

cin>>word[i];

getline(cin,word[i]);

//getline(cin,word[i]);

if (word[i].size()==0)

{

//word[i]="*";

++emp;

return 1;

}

// full string

for (int i=1;i<=n;i++)

{

string temp=word[i];

reverse(temp.begin(),temp.end());

F[gh(temp)]++;

// cout<<gh(temp)<<" %"<<F[gh(temp)]<<endl;

}

for (int i=1;i<=n;i++)

{

string temp=word[i];

long long val1=gh(temp);

reverse(temp.begin(),temp.end());

long long val2=gh(temp);

if (val1==val2)

ans+=F[val1]-1;

else

ans+=F[val1];

}

revs.clear();

//1st is longer

for (int i=1;i<=n;i++)

{

long long P=0;

int sz=word[i].size();

for (int j=sz-1;j>=0;--j)

{

P=P+word[i][j]*pw[sz-j-1];

}

revs[P]++;

}

for (int i=1;i<=n;i++)

{

for (int j=1;j<=word[i].size();j++)

s[j]=s[j-1]+word[i][j-1]*pw[j-1];

s2[word[i].size()+1]=0;

for (int j=word[i].size();j;--j)

{

s2[j]=s2[j+1]+word[i][j-1]*pw[word[i].size()-j];

}

if (word[i].size()>0&&pal(1,word[i].size())==1)

ans+=emp*2;

for (int j=1;j<word[i].size();j++)

{

if (pal(j+1,word[i].size())==0)

continue;

// cout<<i<<" %"<<j<<endl;

long long need=s[j];

int ttl=revs[need];

ans+=ttl;

}

// copy paste

revs.clear();

for (int i=1;i<=n;i++)

reverse(word[i].begin(),word[i].end());

//1st is longer

revs.clear();

//1st is longer

for (int i=1;i<=n;i++)

{

long long P=0;

int sz=word[i].size();

for (int j=sz-1;j>=0;--j)

{

P=P+word[i][j]*pw[sz-j-1];

}

revs[P]++;

}

for (int i=1;i<=n;i++)

{

for (int j=1;j<=word[i].size();j++)

s[j]=s[j-1]+word[i][j-1]*pw[j-1];

s2[word[i].size()+1]=0;

for (int j=word[i].size();j;--j)

{

s2[j]=s2[j+1]+word[i][j-1]*pw[word[i].size()-j];

}

for (int j=1;j<word[i].size();j++)

{

if (pal(j+1,word[i].size())==0)

continue;

long long need=s[j];

int ttl=revs[need];

ans+=ttl;

}

cout<<ans<<endl;

}

//cin.get();cin.get();

return 0;}

Saved diffs

Original text

Open file

/*
*/
 
//#pragma comment(linker, "/STACK:16777216")
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>  
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>
#include <memory.h>
#include <ctime> 
#include <assert.h>
 
#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
 
#define eps 1e-8
#define M_PI 3.141592653589793
#define bs 1000000007
#define bsize 512
 
using namespace std;
 
int tests;
long long pw[1<<24];
int n;
string st;
map<long long, int> F;
string word[1<<24];
map<long long, int> revs;
long long s[1<<24],s2[1<<24];
 
long long gh(string&st)
{
	long long s=0;
	for (int i=0;i<st.size();i++)
		s=s*173+st[i];
	return s;
}
 
bool pal(int l,int r)
{
	long long S1=s[r]-s[l-1];
	long long S2=s2[l]*pw[l-1];
	return (S1==S2);
}
 
int main(){
//freopen("beavers.in","r",stdin);
//freopen("beavers.out","w",stdout);
//freopen("F:/in.txt","r",stdin);
//freopen("F:/output.txt","w",stdout);
ios_base::sync_with_stdio(0);
//cin.tie(0);
 
cin>>tests;
pw[0]=1;
for (int i=1;i<=10000000;i++)
	pw[i]=pw[i-1]*173;
 
for (;tests;--tests)
{
	cin>>n;
	if (n>1000000)
		return 1;
	getline(cin,st);
	F.clear();
	
	long long ans=0;
	
	int emp=0;
	
	for (int i=1;i<=n;i++)
	{
		//cin>>word[i];
		getline(cin,word[i]);
		if (word[i].size()==0)
		{
			//word[i]="*";
			++emp;
			return 1;
		}
	}
	
	// full string
	for (int i=1;i<=n;i++)
	{
		string temp=word[i];
		reverse(temp.begin(),temp.end());
		F[gh(temp)]++;
//		cout<<gh(temp)<<" %"<<F[gh(temp)]<<endl;
	}
	
	for (int i=1;i<=n;i++)
	{
		string temp=word[i];
		long long val1=gh(temp);
		reverse(temp.begin(),temp.end());
		long long val2=gh(temp);
		if (val1==val2)
			ans+=F[val1]-1;
		else
			ans+=F[val1];
	}
	
	revs.clear();
	//1st is longer 
	
	for (int i=1;i<=n;i++)
	{
		long long P=0;
		int sz=word[i].size();
		for (int j=sz-1;j>=0;--j)
		{
			P=P+word[i][j]*pw[sz-j-1];
		}
		revs[P]++;
	}
	
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=word[i].size();j++)
			s[j]=s[j-1]+word[i][j-1]*pw[j-1];
		
		s2[word[i].size()+1]=0;
		
		for (int j=word[i].size();j;--j)
		{
			s2[j]=s2[j+1]+word[i][j-1]*pw[word[i].size()-j];
		}
		
		if (word[i].size()>0&&pal(1,word[i].size())==1)
			ans+=emp*2;
		
		for (int j=1;j<word[i].size();j++)
		{
			if (pal(j+1,word[i].size())==0)
				continue;
//			cout<<i<<" %"<<j<<endl;
			long long need=s[j];
			int ttl=revs[need];
			ans+=ttl;
		}
	}
	
	// copy paste
	revs.clear();
	for (int i=1;i<=n;i++)
		reverse(word[i].begin(),word[i].end());
	//1st is longer 
	revs.clear();
	//1st is longer 
	
	for (int i=1;i<=n;i++)
	{
		long long P=0;
		
		int sz=word[i].size();
		for (int j=sz-1;j>=0;--j)
		{
			P=P+word[i][j]*pw[sz-j-1];
		}
		revs[P]++;
	}
	
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=word[i].size();j++)
			s[j]=s[j-1]+word[i][j-1]*pw[j-1];
		
		s2[word[i].size()+1]=0;
		
		for (int j=word[i].size();j;--j)
		{
			s2[j]=s2[j+1]+word[i][j-1]*pw[word[i].size()-j];
		}
		
		for (int j=1;j<word[i].size();j++)
		{
			if (pal(j+1,word[i].size())==0)
				continue;
			long long need=s[j];
			int ttl=revs[need];
			ans+=ttl;
		}
	}
	
	cout<<ans<<endl;
	
}
 
//cin.get();cin.get();
return 0;}

Changed text

Open file

/*
*/
 
//#pragma comment(linker, "/STACK:16777216")
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>  
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>
#include <memory.h>
#include <ctime> 
#include <assert.h>
 
#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
 
#define eps 1e-8
#define M_PI 3.141592653589793
#define bs 1000000007
#define bsize 512
 
using namespace std;
 
int tests;
long long pw[1<<24];
int n;
string st;
map<long long, int> F;
string word[1<<24];
map<long long, int> revs;
long long s[1<<24],s2[1<<24];
 
long long gh(string&st)
{
	long long s=0;
	for (int i=0;i<st.size();i++)
		s=s*173+st[i];
	return s;
}
 
bool pal(int l,int r)
{
	long long S1=s[r]-s[l-1];
	long long S2=s2[l]*pw[l-1];
	return (S1==S2);
}
 
int main(){
//freopen("beavers.in","r",stdin);
//freopen("beavers.out","w",stdout);
//freopen("F:/in.txt","r",stdin);
//freopen("F:/output.txt","w",stdout);
ios_base::sync_with_stdio(0);
//cin.tie(0);
 
cin>>tests;
pw[0]=1;
for (int i=1;i<=10000000;i++)
	pw[i]=pw[i-1]*173;
 
for (;tests;--tests)
{
	cin>>n;
	if (n>1000000)
		return 1;
	getline(cin,st);
	F.clear();
	
	long long ans=0;
	
	int emp=0;
	
	for (int i=1;i<=n;i++)
	{
		cin>>word[i];
		//getline(cin,word[i]);
		if (word[i].size()==0)
		{
			//word[i]="*";
			++emp;
			return 1;
		}
	}
	
	// full string
	for (int i=1;i<=n;i++)
	{
		string temp=word[i];
		reverse(temp.begin(),temp.end());
		F[gh(temp)]++;
//		cout<<gh(temp)<<" %"<<F[gh(temp)]<<endl;
	}
	
	for (int i=1;i<=n;i++)
	{
		string temp=word[i];
		long long val1=gh(temp);
		reverse(temp.begin(),temp.end());
		long long val2=gh(temp);
		if (val1==val2)
			ans+=F[val1]-1;
		else
			ans+=F[val1];
	}
	
	revs.clear();
	//1st is longer 
	
	for (int i=1;i<=n;i++)
	{
		long long P=0;
		int sz=word[i].size();
		for (int j=sz-1;j>=0;--j)
		{
			P=P+word[i][j]*pw[sz-j-1];
		}
		revs[P]++;
	}
	
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=word[i].size();j++)
			s[j]=s[j-1]+word[i][j-1]*pw[j-1];
		
		s2[word[i].size()+1]=0;
		
		for (int j=word[i].size();j;--j)
		{
			s2[j]=s2[j+1]+word[i][j-1]*pw[word[i].size()-j];
		}
		
		if (word[i].size()>0&&pal(1,word[i].size())==1)
			ans+=emp*2;
		
		for (int j=1;j<word[i].size();j++)
		{
			if (pal(j+1,word[i].size())==0)
				continue;
//			cout<<i<<" %"<<j<<endl;
			long long need=s[j];
			int ttl=revs[need];
			ans+=ttl;
		}
	}
	
	// copy paste
	revs.clear();
	for (int i=1;i<=n;i++)
		reverse(word[i].begin(),word[i].end());
	//1st is longer 
	revs.clear();
	//1st is longer 
	
	for (int i=1;i<=n;i++)
	{
		long long P=0;
		
		int sz=word[i].size();
		for (int j=sz-1;j>=0;--j)
		{
			P=P+word[i][j]*pw[sz-j-1];
		}
		revs[P]++;
	}
	
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=word[i].size();j++)
			s[j]=s[j-1]+word[i][j-1]*pw[j-1];
		
		s2[word[i].size()+1]=0;
		
		for (int j=word[i].size();j;--j)
		{
			s2[j]=s2[j+1]+word[i][j-1]*pw[word[i].size()-j];
		}
		
		for (int j=1;j<word[i].size();j++)
		{
			if (pal(j+1,word[i].size())==0)
				continue;
			long long need=s[j];
			int ttl=revs[need];
			ans+=ttl;
		}
	}
	
	cout<<ans<<endl;
	
}
 
//cin.get();cin.get();
return 0;}