Pagini recente » Cod sursa (job #891896) | Cod sursa (job #598213) | Cod sursa (job #809465) | Cod sursa (job #2977035) | Cod sursa (job #2575506)
#include <stdio.h>
#include <string.h>
#define DIM 2000005
using namespace std;
FILE *fin = fopen("strmatch.in", "r");
FILE *fout = fopen("strmatch.out", "w");
int lgp,n,lg,lps[DIM],nrsol,sol[1005],i;
char patt[DIM],sir[DIM];
int main()
{
fgets(patt+1, 2000003, fin);
fgets(sir+1, 2000003, fin);
patt[0] = sir[0] = 'a';
lgp = strlen(patt)-2;
n = strlen(sir)-2;
lg = 0;
for(i=2; i<=lgp; ++i)
{
while(patt[i] != patt[lg+1] and lg > 0)
lg = lps[lg];
if(patt[i] == patt[lg+1])
++lg;
lps[i] = lg;
}
lg = 0;
for(i=1; i<=n; ++i)
{
while(sir[i] != patt[lg+1] and lg > 0)
lg = lps[lg];
if(sir[i] == patt[lg+1])
lg++;
if(lg == lgp)
{
++nrsol;
if(nrsol <= 1000)
sol[nrsol] = i-lgp;
lg = lps[lg];
}
}
if(nrsol > 1000)
{
fprintf(fout, "%d\n", nrsol);
for(i=1; i<=1000; ++i)
fprintf(fout, "%d ", sol[i]);
}
else
{
fprintf(fout, "%d\n", nrsol);
for(i=1; i<=nrsol; ++i)
fprintf(fout, "%d ", sol[i]);
}
fclose(fin);
fclose(fout);
return 0;
}