Cod sursa(job #733123)

Utilizator pascu_iulianPascu Iulian pascu_iulian Data 11 aprilie 2012 15:10:18
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <stdio.h>
#include <string.h>
#define Max 2000002
using namespace std;

FILE *fin,*fout;

int main(){
	char N[Max],M[Max];
	int n,m,pi[Max],k;
	int pos[1000],p=0;
	
	fin=fopen("strmatch.in","r");
	fout=fopen("strmatch.out","w");
	
	fscanf(fin,"%s", N+1);
	fscanf(fin,"%s", M+1);
	fclose(fin);
	
	m=strlen(M+1);
	n=strlen(N+1);
	
	pi[1]=0;
	k=0;
	for(int i=2;i<=n; i++){
		while(k>0 && N[k+1]!=N[i])
			k=pi[k];
		if(N[k+1]==N[i])
			k++;
		pi[i]=k;
	}
	for(int q=0,i=1;i<=m;i++){
		while(q>0 && N[q+1]!=M[i])
			q=pi[q];
		if(N[q+1]==M[i])
			q++;
		if(q==n){
			if(p>1000) i=m+7;
			else pos[p++]=i-n;
		}
	}	
		
	fprintf(fout,"%d\n",p);
	for(int i=0;i<p;i++)
		fprintf(fout,"%d ",pos[i]);
	return 0;
}