Pagini recente » Cod sursa (job #1674161) | Cod sursa (job #2060396) | Cod sursa (job #1280066) | Cod sursa (job #1427894) | Cod sursa (job #1026053)
#include <cstdio>
#include <cstring>
const int Q=2000006;
char word[Q],text[Q];
int w,t,rez[Q] ;
int gr[Q];
void gres()
{
int f;
for(int i=2; i<=w; i++)
{
if(gr[i-1]==0)
{
if(word[i-1]==word[gr[i-1]])
gr[i]=1;
}
else
{
if(word[i-1]==word[gr[i-1]])
gr[i]=gr[i-1]+1;
else
{
f=gr[gr[i-1]];
while(f!=0)
{
if(word[i-1]==word[f])
{
gr[i]=f+1;
break;
}
f=gr[f];
}
}
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s\n%s",&word,&text);
w=strlen(word);
t=strlen(text);
if(w>t)
{
printf("0");
return 0;
}
gres();
int nr=0,pozact=0;
for(int i=0; i<t; i++)
{
if(pozact==w)
{
nr++;
rez[++rez[0]]=i;
pozact=gr[pozact];
}
if(text[i]==word[pozact])
{
pozact++;
}
else
{
pozact=gr[pozact];
while(pozact!=0)
{
if(text[i]==word[pozact])
{
pozact++;
break;
}
pozact=gr[pozact];
}
if(pozact==0 && text[i]==word[0])
pozact++;
}
}
if(pozact==w)
{
nr++;
rez[++rez[0]]=t;
}
printf("%d\n",nr);
for(int i=1; i<=rez[0]; i++)
{
printf("%d ",rez[i]-w);
}
return 0;
}