Pagini recente » Cod sursa (job #2975485) | Cod sursa (job #1375347) | Cod sursa (job #1978507) | Cod sursa (job #1507649) | Cod sursa (job #1068195)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char n[2000009],m[2000009];
int p[2000009],v[1001],N;
void prefixe()
{
int k,i;
p[1]=0;
k=0;
for(i=2;i<=N;i++)
{
if(k>0&&n[k+1]!=n[i])
k=p[k];
if(n[k+1]==n[i])
k++;
p[i]=k;
}
}
int main()
{
int i,lung,q,nr=0;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%c",&n[1]);
i=1;
while(n[i]!='\n')
{
i++;
scanf("%c",&n[i]);
}
N=i-1;
scanf("%c",&m[1]);
i=1;
while(m[i]!='\n')
{
i++;
scanf("%c",&m[i]);
}
lung=i-1;
prefixe();
q=0;
for(i=1;i<=lung;i++)
{
while(m[i]!=n[q+1]&&q>0)
{
q=p[q];
}
if(m[i]==n[q+1])
{
q++;
}
if(q==N)
{
nr++;
if(nr<=1000)
v[nr]=i-N;
}
}
printf("%d\n",nr);
for(i=1;i<=min(1000,nr);i++)
printf("%d ",v[i]);
return 0;
}