Pagini recente » Cod sursa (job #1765252) | Cod sursa (job #1732073) | Cod sursa (job #487184) | Cod sursa (job #1301104) | Cod sursa (job #1219560)
#include <cstring>
#include <cstdio>
#define maxN 2000013
char S1[maxN], S2[maxN];
int Pi[maxN], d[maxN];
int i,k(0),A,B,sol(0);
void constructie_pi()
{
int k(0),N(strlen(S1)-1),i;
Pi[1]=0;
for (i=2;i<=N;++i){
while (k>0 && S1[i]!=S1[k+1]) k=Pi[k];
if (S1[i]==S1[k+1]) ++k;
Pi[i]=k;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(S1+1,maxN,stdin);
fgets(S2+1,maxN,stdin);
S1[0]=S2[0]=' ';
S1[strlen(S1)-1]=S2[strlen(S2)-1]=0;
A=strlen(S1)-1;
B=strlen(S2)-1;
constructie_pi();
for (i=1;i<=B;++i){
while (k>0 && S2[i] != S1[k+1]) k=Pi[k];
if (S2[i]==S1[k+1]) ++k;
d[i]=k;
if (d[i]==A) ++sol;
}
printf("%d\n",sol);
for (i=1;i<=B;++i)
if (d[i]==A) printf("%d ",i-A);
return 0;
}