Cod sursa(job #383689)

Utilizator Bogdan_CCebere Bogdan Bogdan_C Data 17 ianuarie 2010 17:59:21
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#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;}