Pagini recente » Cod sursa (job #1140400) | Clasament test41241 | Cod sursa (job #149399) | Cod sursa (job #1586125) | Cod sursa (job #154353)
Cod sursa(job #154353)
#include<stdio.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[ 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[ 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)
{
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");
}