Pagini recente » Cod sursa (job #2741258) | Cod sursa (job #1217766) | Cod sursa (job #1207348) | Cod sursa (job #1533979) | Cod sursa (job #1119072)
#include <cstdio>
#include <cstring>
#define Nmax 2000005
using namespace std;
int N,M,pi[Nmax],sol[Nmax];
char a[Nmax],b[Nmax];
inline void Pi()
{
int i,k;
pi[0]=-1; pi[1]=1;
for(i=2;i<N;++i)
{
for(k=pi[i];k>=0 && a[k+1]!=a[i+1];k=pi[k]);
if(k>=0 && a[k+1]==a[i+1])
{
if(k)
pi[i+1]=pi[k]+1;
else
pi[i+1]=1;
}
else
pi[i+1]=0;
}
}
int main()
{
int k=0,i;
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
scanf("%s%s", (a+1),(b+1));
N=strlen(a+1); M=strlen(b+1);
Pi();
for(i=1;i<=M;++i)
{
while(k>=0 && a[k+1]!=b[i])
k=pi[k];
if(k<0 || a[k+1]==b[i])
++k;
if(k==N)
sol[++sol[0]]=i-N;
}
printf("%d\n", sol[0]);
for(i=1;i<=sol[0];++i)
printf("%d ", sol[i]);
printf("\n");
return 0;
}