Pagini recente » Cod sursa (job #1939634) | Cod sursa (job #1958412) | Cod sursa (job #14971) | Cod sursa (job #2488524) | Cod sursa (job #1552519)
#include <cstdio>
#include <cstring>
using namespace std;
char a[2000001], b[2000001];
int phia[2000001], phib[2000001], m, n, nr=0;
int PHI ()
{
int i, k; phia[1]=0;
for (i=2; i<=m; i++)
{
k=phia[i-1];
while (k>0 && a[i]!=a[k+1]) k=phia[k];
if (a[i]==a[k+1]) phia[i]=k+1;
else phia[i]=0;
}
}
int main()
{
int i, k;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(a+1); m=strlen(a+1); a[m+1]=' ';
gets(b+1); n=strlen(b+1);
PHI();
for (i=1; i<=n; i++)
{
k=phib[i-1];
while (k>0 && b[i]!=a[k+1]) k=phia[k];
if (b[i]==a[k+1]) phib[i]=k+1;
else phib[i]=0;
if (phib[i]==m) nr++;
}
printf("%d\n",nr); k=0;
for (i=1; i<=n; i++)
{
if (phib[i]==m) printf("%d ",i-m);
k++;
if (k==1000) break;
}
return 0;
}