Pagini recente » Cod sursa (job #195458) | Cod sursa (job #498264) | Cod sursa (job #2164339) | Cod sursa (job #1740000) | Cod sursa (job #290212)
Cod sursa(job #290212)
//KMP
#include <stdio.h>
#include <string.h>
#define LMAX 2000000
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=-1,x;
p[0]=0;
for (x=1;x<n;x++)
{
while (k>0&&a[k+1]!=a[x]) k=p[k];
if (a[k+1]==a[x]) k++;
p[x]=k;
}
}
int main()
{
citire();
n=strlen(a);
m=strlen(b);
prefix();
int k=-1,nr=0;
int sol[1003];
int i,x;
for (i=0;i<m;i++)
{
while (k>0 && b[i]!=a[k+1]) k=p[k];
if (a[k+1]==b[i]) k++;
if (k==n-1)
{
nr++;
if (nr<1001) sol[nr]=i-n+1;
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;
}