Pagini recente » Cod sursa (job #754487) | Cod sursa (job #98963) | Cod sursa (job #804245) | Cod sursa (job #4608) | Cod sursa (job #383689)
Cod sursa(job #383689)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
#define NMAX 2000000
#define FIN "strmatch.in"
#define FOUT "strmatch.out"
char a[NMAX],b[NMAX];
int next[NMAX],rez[NMAX];
void urm(char *P)
{next[0]=-1;
int k=-1;
int q;
int m=strlen(P);
for(q=1;q<m;q++)
{while(k>-1 && P[k+1]!=P[q]) k=next[k];
if(P[k+1]==P[q]) k++;
next[q]=k;}
}
int main()
{freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
gets(a);
gets(b);
urm(a);
long long i=0,q=-1;
long long contor=0;
for(i=0;i<strlen(b);i++)
{while(q>-1 && a[q+1]!=b[i]) q=next[q];
if(a[q+1]==b[i]) q++;
if(q==strlen(a)-1) {rez[contor]=i-strlen(a)+1;contor++;q=next[q];}}
printf("%d\n",contor);
for(i=0;i<contor;i++) printf("%d ",rez[i]);
return 0;}