Pagini recente » Cod sursa (job #605346) | Cod sursa (job #518464) | Cod sursa (job #507154) | Cod sursa (job #2828054) | Cod sursa (job #1148122)
#include <cstring>
#include <cstdio>
using namespace std;
int i,K,N,M,nr;
char X[1000005],Y[1000005];
int Pi[1000005],d[1000005];
void constructie_pi() //constructia pi-ului
{
N=strlen(X)-1;
K=0;
Pi[1]=0; // trebuie Pi[i]<i deci Pi[1]=0
for (i=2;i<=N;i++)
{
while (K>0&&X[i]!=X[K+1])//cat timp prefixul nu este nul si literele nu coincid sar din K in Pi[K]
K=Pi[K];
if (X[i]==X[K+1]) K=K+1; // daca literele coicid cresc K
Pi[i]=K;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(X+1);
gets(Y+1);
X[0]=' ';
Y[0]=' ';
M=strlen(Y)-1;
constructie_pi();
K=0;
for (i=1; i<=M; i++)
{
while (K>0&&Y[i]!=X[K+1])//cat timp prefixul nu este nul si literele nu coincid sar din K in Pi[K]
K=Pi[K];
if (Y[i]==X[K+1]) K=K+1; // daca literele coincid creste K
d[i]=K;
}
nr=0;
for (i=1;i<=M;i++)
if (d[i]==N) nr++;
printf("%d\n",nr);
for (i=1;i<=M;i++)
if (d[i]==N) printf("%d ",i-N);
return 0;
}