Pagini recente » Cod sursa (job #2701949) | Cod sursa (job #3244523) | Cod sursa (job #3239632) | Cod sursa (job #478453) | Cod sursa (job #679168)
Cod sursa(job #679168)
#include<fstream>
#include<string.h>
#include <iostream>
using namespace std;
int nr,pi[2000002],sol[2000],n,m;
char a[2000002],b[2000002];
void match()
{
int i,w=0;
nr=0;
for (i=0;i<m;i++)
{
while (b[i]!=a[w] && pi[w]!=0)
w=pi[w-1];
if (b[i]==a[w])
w++;
if (w==n)
{
++nr; if (nr<1001) sol[nr]=i-w+1;
w=pi[w-1];
}
}
}
void prefix ()
{
int i;
pi[0]=0;
for (i=1;i<n;i++)
{
pi[i]=pi[i-1];
while (a[pi[i]]!=a[i] && pi[i]!=0)
pi[i]=pi[pi[i]];
if (a[i]==a[pi[i]])
pi[i]++;
}
}
void citire ()
{
FILE *f=fopen ("strmatch.in","r");
fscanf (f,"%s",a);fscanf(f,"%s",b);
n=strlen(a);m=strlen(b);
fclose(f);
}
void afisare ()
{
int i,min;
FILE *f=fopen ("strmatch.out","w");
fprintf (f,"%d\n",nr);
int Min=1000; if (Min>nr) Min=nr;
for (i=1;i<=Min;i++)
fprintf (f,"%d ",sol[i]);
fclose (f);
}
int main ()
{
citire ();
prefix();
match ();
afisare ();
return 0;
}