Cod sursa(job #578505)

Utilizator avram_florinavram florin constantin avram_florin Data 11 aprilie 2011 12:38:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<fstream>

using namespace std;

#define minim(a,b) ((a)<(b)?(a):(b))

const int MaxN = 2000005;
const int MaxX = 1000;

int N,M,nrsol,urm[MaxN],sol[MaxX+5];
char s[MaxN],p[MaxN];

void kmp()
{
	int i,k,q;
	urm[1] = 0;
	k = 0;
	for( q = 2 ; q <= M ; q++ )
		{
			while( k > 0 && p[q] != p[k+1] )
				k = urm[k];
			if( p[q] == p[k+1] )
				k++;
			urm[q] = k;
		}
	q = M+1;
	for( i = 1 ; i <= N ; i++ )
		{
			while( q > 0 && p[q+1] != s[i] )
				q = urm[q];
			if( p[q+1] == s[i] )
				q++;
			if( q == M )
				{
					nrsol++;
					if( nrsol > MaxX )
						continue;
					sol[nrsol] = i-M;
				}
		}
}

int main()
{
	ifstream f ("strmatch.in");
	ofstream g ("strmatch.out");
	f.getline(p+1,MaxN);
	f.getline(s+1,MaxN);
	f.close();
	N = strlen(s+1);
	M = strlen(p+1);
	p[0] = s[0] = ' ';
	kmp();
	int m = minim(nrsol,MaxX);
	g << nrsol << '\n';
	for( int i = 1 ; i <= m ; i++ )
		g << sol[i] << ' ';
	g << '\n';
	g.close();
	return 0;
}