Comparar texto

Encuentra la diferencia entre dos archivos de texto

Editor live
Ocultar sin cambios
Sin ajuste de línea
Vista
Nivel de detalle
Resaltado de sintaxis

Untitled diff

Creado El diff nunca expira
1 eliminación
206 líneas
1 adición
206 líneas
/*
/*
*/
*/
//#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;}
Diferencias guardadas