Pagini recente » Cod sursa (job #1910653) | Cod sursa (job #2817865) | Cod sursa (job #1110709) | Cod sursa (job #348709) | Cod sursa (job #1193128)
#include <cstdio>
#include <cstring>
using namespace std;
#define NMAX 2000010
char A[NMAX],B[NMAX];
int pi[NMAX],sol[NMAX];
int N,M;
void Build_pi()
{
int k=0;
pi[1]=0;
for (int i=2;i<=N;++i)
{
while (k && A[i]!=A[k+1]) k=pi[k];
if (A[k+1]==A[i]) ++k;
pi[i]=k;
}
}
void KMP()
{
int k=0;
Build_pi();
for (int i=1;i<=M;++i)
{
while (k && B[i]!=A[k+1]) k=pi[k];
if (B[i]==A[k+1]) ++k;
if (k==N) sol[++sol[0]]=i-N;
}
printf("%d\n",sol[0]);
for (int i=1;i<=sol[0];++i) printf("%d ",sol[i]);
printf("\n");
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(A+1);
gets(B+1);
N=strlen(A+1);
M=strlen(B+1);
KMP();
return 0;
}