Cod sursa(job #567197)

Utilizator LuffyBanu Lavinia Luffy Data 29 martie 2011 20:04:58
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<stdio.h>
#include<string.h>
#define dim 2000003
using namespace std;

int i,a,b,m,n,k,num,urm[dim],v[dim],K;
char A[dim],B[dim];

void urmatorul()
{k=1;

while(k<m)
{
  if(A[a]==A[k]) {num++; urm[k]=num; a++; k++;}
  else {num=0; a=0;
		if(A[a]==A[k]) {num++; a++; urm[k]=num;}
        k++;}
	
}


}


void potrivire()
{int k=a,p=b;

while(A[k] == B[p])
{k++; p++;}

a=k;
	

}


int main()
{
 FILE *f=fopen("strmatch.in","r"), *g=fopen("strmatch.out","w");
 
 fgets(A,dim,f);
 fgets(B,dim,f);
 m=strlen(A); m--;
 n=strlen(B); n--;
 
 urmatorul();
 
 a=0;
 while(b<=n)
 {if(B[b]==A[a]) potrivire();
  if(a==m) 
	   {K++; v[K]=b;}

 b+=(a-urm[a])+1; a=0;}
	 

 fprintf(g,"%d\n",K);
  for(i=1; i<=K; i++)
	fprintf(g,"%d ",v[i]);
 
 
fclose(f);
fclose(g);
return 0;
}