Nu aveti permisiuni pentru a descarca fisierul grader_test9.in
Cod sursa(job #519889)
Utilizator | Data | 6 ianuarie 2011 19:44:26 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.39 kb |
#include <stdio.h>
#include <string.h>
#define IN "strmatch.in"
#define OUT "strmatch.out"
#define LEN_S 2097152
#define LEN_Sol 2048
FILE *fin=fopen(IN,"r");
FILE *fout=fopen(OUT,"w");
char a[LEN_S],b[LEN_S];
long v[LEN_S];
long poz[LEN_Sol];
long sol;
long c,lung,lungg;
int sw=1;
void calc();
int verif(long );
int main()
{
long long i;
fscanf(fin,"%s %s",a,b);
fclose(fin);
calc();
lung=strlen(b);
lungg=strlen(a);
for(i=lungg-1;i<=lung-1;i++)
if(v[i]==c && b[i]==a[lungg-1] && b[i-lungg+1]==a[0])
{
if(sw==1)
{
if(sol<=1000)
{
sol++;
poz[sol]=i-lungg+1;
}
else
sol++;
}
else
if(verif(i)==1)
{
if(sol<=1000)
{
sol++;
poz[sol]=i-lungg+1;
}
else
sol++;
}
}
fprintf(fout,"%ld\n",sol);
for(i=1;(i<=sol && i<=1000);i++)
fprintf(fout,"%ld ",poz[i]);
fclose(fout);
return 0;
}
void calc()
{
long i;
long auxa=strlen(a);
long auxb=strlen(b);
c=0;
for(i=0;i<auxa;i++)
c=c+a[i];
for(i=1;i<auxa;i++)
if(a[i]!=a[0])
{
sw=2;
break;
}
v[0]=b[0];
for(i=1;i<auxa;i++)
v[i]=v[i-1]+b[i];
for(i=auxa;i<auxb;i++)
v[i]=v[i-1]+b[i]-b[i-auxa];
}
int verif(long i)
{
long j;
long z=lungg-1;
for(j=i;j>=i-lungg+1;j--)
if(b[j]!=a[z--])
return 0;
return 1;
}