Cod sursa(job #961275)

Utilizator superman_01Avramescu Cristian superman_01 Data 11 iunie 2013 20:37:18
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<fstream>
#include<cstring>
#include<vector>

#define MAX_SIZE 2000005
#define get_min(a,b) ((a)>(b)?(a):(b))

using namespace std;

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

typedef vector<int>::iterator IT;

char sir1[MAX_SIZE],sir2[MAX_SIZE];
int N,M,pref[MAX_SIZE]; 
vector<int> Sol;

void Read ( void )
{  
	sir1[0]=' ';
	sir2[0]=' ';
	f>>(sir1+1)>>(sir2+1);
	M=strlen(sir1)-1;
	N=strlen(sir2)-1;
	f.close();	
}
void MakePrefix( void )
{
	pref[1]=0;
	for(int i(2) ,q(0) ; i <= M ; ++i )
	{
		while(q && sir1[q+1] != sir1[i] )
			q=pref[q];
		if(sir1[q+1] == sir1[i] )
			++q;
		pref[i]=q;
	}
}
void KMP ( void )
{
	for(int i(1),q(0) ; i <= N ; ++i )
	{
		while(q && sir1[q+1] != sir2[i] )
			q=pref[q];
		if( sir1[q+1] == sir2[i] )
			++q;
		if( q ==  M )
		{
			q=pref[M];
		    Sol.push_back(i-M);			
		}
	}
}
void Solve ( void )
{
	MakePrefix();
	KMP();
}
void Write ( void )
{
	g<<Sol.size()<<"\n";
	int cnt(0);
	for(IT it=Sol.begin() ; cnt <= 1000 && it!= Sol.end() ; ++it,++cnt)
		 g<<*it<<" ";
	g.close();
}
int main ( void )
{
	Read();
	Solve();
	Write();
	return 0;
}