Pagini recente » Cod sursa (job #2894877) | Cod sursa (job #1256841) | Cod sursa (job #1080951) | Cod sursa (job #1553855) | Cod sursa (job #305972)
Cod sursa(job #305972)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 200000
char t[MAXN],p[MAXN];
int pref[MAXN];int ok[1000];
int matchNo=0;
int KMP(char *t,char *p,int *pref)
{
int i,q;
q=-1;
for (i=0;i<strlen(t);i++)
{
while ((q>=0)&&(p[q+1]!=t[i])) q=pref[q];
if (p[q+1]==t[i]) q++;
if (q==strlen(p)-1)
{
ok[matchNo++]=i-strlen(p)+1;
q=pref[q];
}
}
return matchNo;
}
void preCompute(char *p,int *pref)
{
int i,q;
q=-1;
pref[0]=-1;
for (i=1;i<strlen(p);i++)
{
while ((q>=0)&&(p[q+1]!=p[i])) q=pref[q];
if (p[q+1]==p[i]) q++;
pref[i]=q;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",p);
scanf("%s",t);
preCompute(p,pref);
printf("%d\n",KMP(t,p,pref));
int i;
if (matchNo<1000)
for (i=0;i<matchNo;i++) printf("%d ",ok[i]);
fclose(stdout);
return 0;
}