Pagini recente » Cod sursa (job #980554) | Cod sursa (job #254813) | Cod sursa (job #2419221) | Cod sursa (job #2714807) | Cod sursa (job #126601)
Cod sursa(job #126601)
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
#define maxn 512
char a[maxn],b[maxn];
long v[512][512],n,m,max2= 0,n2,m2;
char r[512][512],q[512][512];
int sortsir( const void *a, const void *b)
{
return strcmp( (char *)a, (char *) b);
}
long cauta( long poz)
{
long st = 0;
long dr = m2-1;
while( st != dr)
{
long mij = (st + dr) /2;
if( strcmp(q[poz],r[mij]) > 0)
st = mij+1;
else dr = mij;
}
return !(strcmp(q[poz],r[st]));
}
int main()
{
freopen("subsir.in","r",stdin);
freopen("subsir.out","w",stdout);
scanf("%s %s",a,b);
n = strlen(a);
m = strlen(b);
for(long i = 0; i < m; i++)
v[0][i] = (a[0] == b[i]);
for(long j = 0; j < n; ++j)
v[j][0] = (b[0] == a[j]);
for( long i = 1; i < n; i++)
for( long j = 1; j < m; ++j)
{
if(a[i] != b[j])
v[i][j] = 0;
else
{
v[i][j] = 1 + v[i-1][j-1];
if( v[i][j] > max2 )
max2 = v[i][j];
}
}
//printf("%ld\n",max);
for(long i = 0; i<= n-max2; ++i)
strncpy(q[i],a+i,max2);
for(long j = 0; j<= m-max2; ++j)
strncpy(r[j],b+j,max2);
qsort(q,n-max2+1,sizeof(q[0]),sortsir);
qsort(r,m-max2+1,sizeof(q[0]),sortsir);
//sort(q,q+n-max2);
//sort(r,r+m-max2);
n2 = n-max2+1;
m2 = m-max2+1;
long sol = cauta(0);
for( long i = 1; i < n2 ; ++i)
{
if( strcmp(q[i],q[i-1])!=0)
sol+=cauta(i);
}
printf("%ld\n",sol);
}