Pagini recente » Cod sursa (job #3144990) | Cod sursa (job #1046380) | Cod sursa (job #319774) | Cod sursa (job #588) | Cod sursa (job #154335)
Cod sursa(job #154335)
#include<stdio.h>
#define INPUT "strmatch.in"
#define OUTPUT "strmatch.out"
#define NMax 2000001
FILE *fin=fopen(INPUT, "r"),*fout=fopen(OUTPUT, "w");
long lg1, lg2;
long prefix[ NMax ], final[ 1001 ], 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()
{
char ch;
fscanf(fin, "%c", &ch);
lg1 = 0;
while(ch != '\n')
{
sir1[ lg1++ ] = ch;
fscanf(fin, "%c", &ch);
}
fscanf(fin, "%c", &ch);
lg2 = 0;
while(ch != '\n' && !feof( fin ) )
{
sir2[ lg2++ ] = ch;
fscanf(fin, "%c", &ch);
}
}
void calculPrefix()
{
long poz;
prefix[ 0 ] = 0;
poz = 0;
for( long i = 1; i < lg1; ++i)
{
while(poz > 0 && sir1[ poz ] != sir1[ i ])
poz = prefix[ poz ];
if( sir1[ poz ] == sir1[ i ] )
++poz;
prefix[ i ] = poz;
}
}
void KMP()
{
long poz;
poz = 0;
nrTotal = -1;
for( long i = 0; i < lg2; ++i)
{
while(poz > 0 && sir1[ poz ] != sir2[ i ] )
poz = prefix[ poz ];
if(sir1[ poz ] == sir2[ i ])
++poz;
if(poz == lg1)
{
if(nrTotal < 1000)
final[ ++nrTotal ] = i - lg1 + 1;
poz = prefix[ poz - 1 ];
}
}
printSolution();
}
void printSolution()
{
fprintf(fout, "%ld\n", nrTotal + 1);
for( long i = 0; i <= nrTotal; ++i)
fprintf(fout, "%ld ", final[ i ]);
fprintf(fout, "\n");
}