Pagini recente » Cod sursa (job #1659109) | Cod sursa (job #2083454) | Cod sursa (job #2679252) | Cod sursa (job #1326825) | Cod sursa (job #1148147)
#include <cstring>
#include <cstdio>
using namespace std;
int i,K,N,M,nr,c;
char X[2000005],Y[2000005];
int Pi[2000005],d[2000005];
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);
c=0;
for (i=1;i<=M;i++)
if (d[i]==N)
{
printf("%d ",i-N);
c++;
if (c==1000) break;
}
return 0;
}