Pagini recente » Cod sursa (job #1046574) | Cod sursa (job #484715) | Cod sursa (job #1423139) | Cod sursa (job #1030233) | Cod sursa (job #1552517)
/*
v1 = B M
v2 = A N
construiesc phi pt A
for(i=1; i<=m; ++i)
{
k=v[i-1];
while(k>0&&b[i]!=a[k+1])
{
k=phi[k];
}
if (b[i]==a[k+1])v[i]=k+1;
else v[i]=0;
}
*/
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2000000 + 5;
int phib[NMAX],phia[NMAX];
char a[NMAX],b[NMAX];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(a+1);
gets(b+1);
phia[1]=0;
int len1=strlen(a+1);
int len2=strlen(b+1);
int k;
for (int i = 2; i<=len1; ++i)
{
k = phia[i-1];
while(k>0&&a[k+1]!=a[i])
{
k=phia[k];
}
if (a[i]==a[k+1])phia[i]=k+1;
else phia[i]=0;
}
for (int i = 1; i<=len2; ++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;
}
int nr = 0 ;
for (int i = 1; i<=len2; ++i)
{
if (phib[i]==len1)
++nr;
}
printf("%d\n",nr);
int x = 1000;
for (int i = 1; i<=len2 && x>0; ++i,--x)
{
if (phib[i]==len1)
{
printf("%d ",i-len1);
}
}
printf("\n");
return 0;
}