Pagini recente » Cod sursa (job #1805040) | Cod sursa (job #1414560) | Cod sursa (job #1539962) | Cod sursa (job #2926833) | Cod sursa (job #298145)
Cod sursa(job #298145)
#include<stdio.h>
#include<string.h>
#define LMAX 2000002
char s[LMAX],p[LMAX];
int i,numar,n,m,pi[LMAX];
int v[1010];
int main(void)
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",p+1);
scanf("%s",s+1);
n=strlen(s+1);
m=strlen(p+1);
//int *pi=new int[(m+1)*sizeof(int)];
pi[1]=0;
int k=0;
for(i=2;i<=m;i++)
{
while(k>0&&p[k+1]!=p[i])
k=pi[k];
if(p[k+1]==p[i])
k++;
pi[i]=k;
}
int q=0;
for(i=1;i<=n;i++)
{
while(q>0&&p[q+1]!=s[i])
q=pi[q];
if(p[q+1]==s[i])
q++;
if(q==m)
{
numar++;
if(numar<=1000)
{
v[numar]=i-m;
}
q=pi[q];
}
}
printf("%d\n",numar);
numar=numar>1000?1000:numar;
for(i=1;i<=numar;i++)
printf("%d ",v[i]);
printf("\n");
fclose(stdin);
fclose(stdout);
return 0;
}