Pagini recente » Cod sursa (job #806498) | Cod sursa (job #3194296) | Cod sursa (job #1029078) | Cod sursa (job #2004696) | Cod sursa (job #125250)
Cod sursa(job #125250)
#include <stdio.h>
#include <string.h>
char c[17];
int n,i,j,k,nr;
short int a[36001][27],b[36001][27];
short int val[36001];
void inter(int p, int q, int lvl)
{
int r=(p+q)/2,x,y,s,i;
x=p;y=r+1;k=0;
while (x<=r && y<=q)
{
if (a[x][lvl]<a[y][lvl])
{
k++;
for (s=lvl; s<=27; s++)
b[k][s]=a[x][s];
x++;
}
else
{
k++;
for (s=lvl; s<=27; s++)
b[k][s]=a[y][s];
y++;
}
}
while (x<=r)
{
k++;
for (s=lvl; s<=27; s++)
b[k][s]=a[x][s];
x++;
}
while (y<=q)
{
k++;
for (s=lvl; s<=27; s++)
b[k][s]=a[y][s];
y++;
}
k=0;
for (i=p; i<=q; i++)
{
k++;
for (s=lvl; s<=27; s++)
a[i][s]=b[k][s];
}
}
void merge(int p, int q, int lvl)
{
int r=(p+q)/2;
if (p==q) return;
merge(p,r,lvl);
merge(r+1,q,lvl);
inter(p,q,lvl);
if (q<=p+1) return;
}
int main()
{
freopen("restante.in","r",stdin);
freopen("restante.out","w",stdout);
scanf("%d",&n);
for (i=1; i<=n; i++)
{
scanf("%s",c);
for (j=0; j<=strlen(c)-1; j++)
a[i][int(c[j]-96)]++;
}
for (i=0; i<=26; i++)
{
for (j=1; j<=27; j++)
a[0][j]=a[1][j];
int p1=1,p2=0;
for (j=1; j<=n; j++)
{
int t;
int gas=1;
for (t=0; t<=i; t++)
if (a[j][t]!=a[j-1][t])
{
gas=0;
break;
}
if (gas==1) p2++;
else
{
if (p1!=p2) merge(p1,p2,i+1);
p1=j;p2=j;
}
}
if (p2==n && p1!=p2) merge(p1,p2,i+1);
}
nr=0;
for (i=1; i<=27; i++)
a[0][i]=0;
for (i=1; i<=n-1; i++)
{
int gas=1;
for (j=1; j<=27; j++)
if (a[i][j]!=a[i+1][j])
{
gas=0;
break;
}
if (gas==1)
{
val[i]=1;
val[i+1]=1;
}
}
for (i=1; i<=n; i++)
if (!val[i]) nr++;
printf("%d\n",nr);
return 0;
}