Pagini recente » Cod sursa (job #1603567) | Cod sursa (job #486644) | Cod sursa (job #1454767) | Cod sursa (job #271012) | Cod sursa (job #1261079)
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 2000003
char x[MAXN], y[MAXN];
int Pi[MAXN],d[MAXN];
int i,k,N,M;
void constructie_pi() // construim pi-ul
{
N=strlen(x)-1;
Pi[1]=0;
k=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
k=Pi[k]; // sar din k la Pi[k]
if(x[i]==x[k+1])
k++;
Pi[i]=k;
}
}
int main ()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(x+1, MAXN, stdin);
fgets(y+1, MAXN, stdin);
x[0] = ' '; y[0] = ' ';
x[strlen(x)-1] = y[strlen(y)-1] = 0;
M=strlen(y)-1;
constructie_pi(); //construim pi-ul
k=0;
for(i=1; i<=M; i++)
{
while(k>0 && y[i]!=x[k+1])
k=Pi[k];
if(y[i]==x[k+1])
k++;
d[i]=k;
}
int NR = 0;
for(int i=1;i<= M;++i)
if(d[i] == N)
NR++;
printf("%d\n",NR);
for(int i=1;i<= M;++i)
if(d[i] == N)
printf("%d ",i-N);
return 0;
}