Cod sursa(job #126601)

Utilizator marius135Dumitran Adrian Marius marius135 Data 22 ianuarie 2008 15:37:44
Problema Subsir Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#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);
}