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

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;}