Pagini recente » Cod sursa (job #960005) | Cod sursa (job #58462) | Cod sursa (job #2513995) | Cod sursa (job #1810912) | Cod sursa (job #1496067)
#include<cstdio>
#include<cstring>
#include<algorithm>
int pi[2000002],rasp[1001];
char p[2000002],s[2000002];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",p,s);
int n=strlen(p);
for(int i=n;i>=1;i--)
p[i]=p[i-1];
int m=strlen(s);
for(int i=m;i>=1;i--)
s[i]=s[i-1];
pi[1]=0;
for(int i=2;i<=n;i++)
{
int k=pi[i-1];
while(k>0 && p[i]!=p[k+1])
k=pi[k];
if(p[i]==p[k+1])
pi[i]=k+1;
else
pi[i]=0;
}
/*for(int i=1;i<=n;i++)
printf("%d ",pi[i]);*/
int k=0,poz=0;
for(int i=1;i<=m;i++)
{
while(k>0 && s[i]!=p[k+1])
k=pi[k];
if(s[i]==p[k+1])
k++;
if(k==n)
{
if(poz<1000)
rasp[++poz]=i-n;
else
poz++;
}
}
/*for(int i=1;i<=m;i++)
printf("%d ",d[i]);*/
printf("%d\n",poz);
poz=std::min(poz,1000);
for(int i=1;i<=poz;i++)
printf("%d ",rasp[i]);
fclose(stdin);
fclose(stdout);
return 0;
}