Cod sursa(job #518009)

Utilizator mvbinfoDragos Dinca mvbinfo Data 30 decembrie 2010 13:14:23
Problema Potrivirea sirurilor Scor 28
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<stdio.h>
#include<string.h>
using namespace std;
#define Max  2000000

int urm[Max],nr,v[Max];
char T[Max],P[Max];
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", P);	fscanf(f,"%s", T);	
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++)
		if(v[i]<=1000)
		fprintf(g,"%d ",v[i]);
	fprintf(g,"\n");

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