Pagini recente » Monitorul de evaluare | Cod sursa (job #684865) | Cod sursa (job #758279) | Cod sursa (job #2115544) | Cod sursa (job #291108)
Cod sursa(job #291108)
#include <stdio.h>
#include <string.h>
using namespace std;
#define LMAX 2000018
int n,m,p[LMAX];
char a[LMAX],b[LMAX];
void citire()
{
FILE *fin=fopen("strmatch.in","r");
fscanf(fin,"%s",&a);
fscanf(fin,"%s",&b);
fclose(fin);
}
void prefix()
{
int k=0,x;
p[0]=0;
for (x=2;x<=n;++x)
{
while (k>0&&a[k]!=a[x-1]) k=p[k];
if (a[k]==a[x-1]) k++;
p[x]=k;
}
}
int main()
{
citire();
n=strlen(a)-1;
m=strlen(b)-1;
prefix();
int k=0,nr=0;
int sol[1008];
int i;
for (i=1;i<=m;++i)
{
while (k>0 && b[i-1]!=a[k]) k=p[k];
if (a[k]==b[i-1]) k++;
if (k==n)
{
nr++;
if (nr<1001) sol[nr]=i-n;
k=p[k];
}
}
FILE *fout=fopen("strmatch.out","w");
fprintf(fout,"%d\n",nr);
if (nr>1000) nr=1000;
for (i=1;i<=nr;i++)
fprintf(fout,"%d ",sol[i]);
fclose(fout);
return 0;
}