Pagini recente » Cod sursa (job #2241796) | Cod sursa (job #2291888) | Cod sursa (job #665372) | Cod sursa (job #1645003) | Cod sursa (job #154372)
Cod sursa(job #154372)
#include<stdio.h>
#include<string.h>
#define INPUT "strmatch.in"
#define OUTPUT "strmatch.out"
#define NMax 2000005
FILE *fin=fopen(INPUT, "r"),*fout=fopen(OUTPUT, "w");
long lg1, lg2;
long prefix[ NMax ], final[ 1005 ], nrTotal;
char sir1[ NMax ], sir2[ NMax ];
void readValues();
void calculPrefix();
void KMP();
void printSolution();
int main()
{
readValues();
calculPrefix();
KMP();
fclose(fin);
fclose(fout);
return 0;
}
void readValues()
{
fgets(sir1,sizeof(sir1),fin);
fgets(sir2,sizeof(sir2),fin);
lg1 = 0;
for(long i = strlen(sir1) - 1; i >= 0; --i)
if(( sir1[ i ] >= 'A' && sir1[ i ] <='Z') || (sir1[ i ] >= 'a' && sir1[ i ] <='z') || (sir1[ i ] >= '0' && sir1[ i ] <= '9') ){
sir1[ i + 1 ] = sir1[ i ];
if( lg1 < i )
lg1 = i+1;
}
sir1[0] = ' ';
lg2 = 0;
for(long i = strlen(sir2) - 1; i >= 0; --i)
if(( sir2[ i ] >= 'A' && sir2[ i ] <='Z') || (sir2[ i ] >= 'a' && sir2[ i ] <='z') || (sir2[ i ] >= '0' && sir2[ i ] <= '9') ){
sir2[ i + 1 ] = sir2[ i ];
if( lg2 < i )
lg2 = i+1;
}
sir2[0] = ' ';
}
void calculPrefix()
{
long poz;
prefix[ 1 ] = 0;
poz = 0;
for( long i = 2; i <= lg1; ++i)
{
while(poz > 0 && sir1[ poz + 1 ] != sir1[ i ])
poz = prefix[ poz ];
if( sir1[ poz + 1 ] == sir1[ i ] )
++poz;
prefix[ i ] = poz;
}
}
void KMP()
{
long poz;
poz = 0;
nrTotal = 0;
for( long i = 1; i <= lg2; ++i)
{
while(poz > 0 && sir1[ poz + 1 ] != sir2[ i ] )
poz = prefix[ poz ];
if(sir1[ poz + 1 ] == sir2[ i ])
++poz;
if(poz == lg1)
{
++nrTotal;
if(nrTotal <= 1000)
final[ nrTotal ] = i - lg1;
poz = prefix[ poz ];
}
}
printSolution();
}
void printSolution()
{
fprintf(fout, "%ld\n", nrTotal);
for( long i = 1; i <= nrTotal; ++i)
fprintf(fout, "%ld ", final[ i ]);
fprintf(fout, "\n");
}