Cod sursa(job #930431)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 27 martie 2013 17:26:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include<fstream>
#include<string.h>

#define max_l 4000900

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

char a[max_l] , b[max_l/2];
int La , Lb , i , fail , P[max_l] , nr , Sol[1010] , ok =1;
void read(){
	f>>(a+1)>>b;
	La = strlen(a+1);
	Lb = strlen(b);
	a[La+1] = '*'; strcpy(a+La+2 , b);
}

void solve(){
	
	P[1] = 0;
	
	for(i = 2 ; i <= La + Lb + 1 ; i++){
		fail = P[i-1];
		while(a[fail+1]!=a[i]&&fail!=0)
			fail = P[fail];
		if(a[fail+1] == a[i])
			P[i] = fail+1;
		if(P[i] == La){
			nr++;
			if(ok)
				Sol[nr] = i - La - 1;
			if(nr == 1000)
				ok = 0;
		}
	}
	
}

void print(){
	
	g<<nr<<"\n";
	for(i=1;i<=nr&&i<=1000;i++)
		g<<Sol[i]-La<<" ";
	
}

int main(){
	
	read();
	
	solve();
	
	print();
	
	return 0;
}