Compare text

Find the difference between two text files

Real-time editor
Hide unchanged lines
Disable line wrap
Layout
Diff precision
Syntax highlighting

Untitled diff

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