Cod sursa(job #383702)

Utilizator Bogdan_CCebere Bogdan Bogdan_C Data 17 ianuarie 2010 18:39:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
#define NMAX  2000005
#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);
int i=0,q=-1;
int contor=0;
int M=0,N=0;

   for (; (a[M] >= 'A' && a[M] <= 'Z') || (a[M] >= 'a' && a[M] <= 'z')
            || (a[M] >= '0' && a[M] <= '9'); ++M);
   for (; (b[N] >= 'A' && b[N] <= 'Z') || (b[N] >= 'a' && b[N] <= 'z')
            || (b[N] >= '0' && b[N] <= '9'); ++N);                  
        
for(i=0;i<N;i++)
 {while(q>-1 && a[q+1]!=b[i]) q=next[q];
  if(a[q+1]==b[i]) q++;
  if(q==M-1) {if(contor<1001) {rez[contor]=i-M+1;}contor++;q=next[q];}}
printf("%d\n",contor);
for(i=0;i<contor && i<1000;i++) printf("%d ",rez[i]);  
   return 0;}