Pagini recente » Cod sursa (job #1395360) | Cod sursa (job #2598331) | Cod sursa (job #3004948) | Cod sursa (job #1537561) | Cod sursa (job #512432)
Cod sursa(job #512432)
#include<stdio.h>
#include<string.h>
#define LMT 2000006
char s[LMT];
char p[LMT];
int pi[LMT];
int n,m,nrp;
int poz[1006];
int main ()
{
int i,q=0;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
s[0]=p[0]=' ';
fgets(p+1,sizeof(p)-1,stdin);
fgets(s+1,sizeof(s)-1,stdin);
n=strlen(s+1);
m=strlen(p+1);
while(!((s[n]>='a' && s[n]<='z')
|| (s[n]>='A' && s[n]<='Z')
|| (s[n]>='0' && s[n]<='9')))
n--;
while(!((p[m]>='a' && p[m]<='z')
|| (p[m]>='A' && p[m]<='Z')
|| (p[m]>='0' && p[m]<='9')))
m--;
for(i=2;i<=m;i++)
{
while(q>0 && p[q+1]!=p[i])
q=pi[q];
if(p[q+1]==p[i])
q++;
pi[i]=q;
}
q=0;
for(i=1;i<=n;i++)
{
while (q>0 && s[i]!=p[q+1])
q=pi[q];
if (s[i]==p[q+1])
q++;
if (q==m)
{
poz[++nrp]=i-m;
if(nrp==1000)
break;
q=pi[q];
}
}
printf("%d\n",nrp);
for(i=1;i<=nrp;i++)
printf("%d ",poz[i]);
printf("\n");
return 0;
}