Pagini recente » Cod sursa (job #2455245) | Cod sursa (job #2781031) | Cod sursa (job #2473077) | Cod sursa (job #2336613) | Cod sursa (job #445656)
Cod sursa(job #445656)
#include<cstdio>
#include<cstring>
#define L 2000010
char A[L],B[L];
int a,b,i,n,P[L],X[1001],cnt;
void read(), solve(),prefix(),KMP();
int main()
{
read();
solve();
return 0;
}
void read()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",A+1);
scanf("%s",B+1);
a=strlen(A+1);
b=strlen(B+1);
}
void solve()
{
prefix();
KMP();
n=1000<cnt?1000:cnt;
printf("%d\n",cnt);
for(i=1;i<=cnt;i++)
printf("%d ",X[i]);
}
void prefix()
{
int k=0;
for(i=2;i<=a;i++)
{
while(k&&A[k+1]!=A[i])
k=P[k];
if(A[k+1]==A[i])
k++;
P[i]=k;
}
}
void KMP()
{
int k=0;
for(i=1;i<=b;i++)
{
while(k&&B[i]!=A[k+1])
k=P[k];
if(B[i]==A[k+1])
k++;
if(k==a)
{
cnt++;
if(cnt<=1000)
X[cnt]=i-a;
k=P[k];
}
}
}