Cod sursa(job #1166060)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 3 aprilie 2014 10:38:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<fstream>
#include<cstring>

using namespace std;

#define max_n 2000010

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

char A[2*max_n] , B[max_n];
int LA , LB , P[2*max_n] , k , Sol[max_n] , fail;

void read(){

	f>>A+1>>B;

	LA = strlen(A+1);
	LB = strlen(B);

	A[LA+1] = '*';

	strcpy( A + LA + 2 , B );

}

int main(){

	read();

	P[1] = 0;

	for( int 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 ){
			k++;
			if( k <= 1000 )
				Sol[k] = i - 2 * LA - 1;

		}

	}

	end:

	g<<k<<"\n";

	for( int i = 1 ; i <= k && i <= 1000 ; i++ )
		g<<Sol[i]<<" ";

	return 0;
}