Pagini recente » Cod sursa (job #2059624) | Cod sursa (job #1281231) | Cod sursa (job #2167756) | Cod sursa (job #2386579) | Cod sursa (job #1571750)
#include <cstdio>
#include <cstring>
using namespace std;
int phi1[2000005], phi2[2000005], n,m,i,k,nr,nr2;
char a[2000005], b[2000005];
void phi()
{
int i,k;
k=0;
phi1[1]=0;
for(i=2;i<=n;i++)
{
while(k>0&&a[k+1]!=a[i])
k=phi1[k];
if(a[k+1]==a[i])k++;
phi1[i]=k;
}
}
int main()
{
// freopen("strmatch.in","r",stdin);
// freopen("strmatch.out","w",stdout);
gets(a+1);
gets(b+1);
n=strlen(a+1);
m=strlen(b+1);
phi();
k=0;
for(i=1;i<=m;i++)
{
while(k>0&&a[k+1]!=b[i])
k=phi1[k];
if(a[k+1]==b[i])k++;
phi2[i]=k;
}
for(i=1;i<=m;i++)
{
if(phi2[i]==n)nr++;
}
printf("%d\n",nr);
for(i=n;i<=m;i++)
{
if(phi2[i]==n)
{
printf("%d ",i-n);
nr2++;
if(nr2==1000)break;
}
}
return 0;
}