Pagini recente » Cod sursa (job #1613648) | Cod sursa (job #1388774) | Cod sursa (job #3143914) | Cod sursa (job #3290750) | Cod sursa (job #305980)
Cod sursa(job #305980)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAXN 300000
char t[MAXN],p[MAXN],n=0,m=0;
int pref[MAXN];int ok[MAXN];
int matchNo=0;
int KMP(char *t,char *p,int *pref)
{
int i,q;
q=-1;
for (i=0;i<m;i++)
{
while ((q>=0)&&(p[q+1]!=t[i])) q=pref[q];
if (p[q+1]==t[i]) q++;
if (q==n-1)
{
ok[matchNo++]=i-n+1;
q=pref[q];
}
}
return matchNo;
}
void preCompute(char *p,int *pref)
{
int i,q;
q=-1;
pref[0]=-1;
for (i=1;i<n;i++)
{
while ((q>=0)&&(p[q+1]!=p[i])) q=pref[q];
if (p[q+1]==p[i]) q++;
pref[i]=q;
}
}
int main()
{
int i;
char c;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
for (;;)
{
c=fgetc(stdin);
if (isalnum(c))
p[n++]=c;
else
break;
}
for (;;)
{
c=fgetc(stdin);
if (isalnum(c)) break;
}
t[m++]=c;
for (;;)
{
c=fgetc(stdin);
if (isalnum(c))
t[m++]=c;
else
break;
}
preCompute(p,pref);
printf("%d\n",KMP(t,p,pref));
if (matchNo<1000)
for (i=0;i<matchNo;i++) printf("%d ",ok[i]);
fclose(stdout);
return 0;
}