Cod sursa(job #517994)

Utilizator mvbinfoDragos Dinca mvbinfo Data 30 decembrie 2010 12:57:18
Problema Potrivirea sirurilor Scor 8
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<stdio.h>
#include<string.h>
using namespace std;
#define nMax 1000
#define mMax 255
int urm[mMax],nr,v[nMax];
char T[nMax],P[mMax];
int n,m;


void urmatorul (char *p)
{
	int k=-1, x;
	urm[0]=0;
	for(x=1;x<m;x++)
	{	
		while(k>0 && P[k+1]!=P[x])
			k=urm[k];
		
		if(P[k+1]==P[x]) 
			k++;
		
		urm[x]=k;	
	}	

}


int main()
{
	FILE *f=fopen("strmatch.in","r"), *g=fopen("strmatch.out","w");
	
int i,x=-1;
	
fscanf(f,"%s", T);	fscanf(f,"%s", P);	
n=strlen(T);	m=strlen(P);

urmatorul(P);

for(i=0;i<n;i++)
	{	
		while(x>0 && P[x+1]!=T[i])
			x=urm[x];
		
		if(P[x+1]==T[i]) 
			x++;	//s-au potrivit
		
		if(x==m-1)
		{
		nr++;
		v[nr]=i-m+1;
		//printf("Am gasit subsirul in pozitia %d\n",i-m+1);
		
		x=urm[x];
		}

	}	
	fprintf(g,"%d\n",nr);
	for(i=1;i<=nr;i++)
		fprintf(g,"%d ",v[i]);
	fprintf(g,"\n");

fclose(f);
fclose(g);
return 0;
}