Cod sursa(job #662421)

Utilizator XbyteAvram Florin Xbyte Data 16 ianuarie 2012 18:14:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<fstream>
#include<cstdio>
#include<cstring>

using namespace std;

const int MaxN = 2000001;
const int MaxM = 1001;

const char InFile[] = "strmatch.in";
const char OutFile[] = "strmatch.out";

int n,m,nrsol,urm[MaxN],sol[MaxM];
char S[MaxN],P[MaxN];

ifstream fin(InFile);
ofstream fout(OutFile);

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 && S[i] != P[q+1] )
				q = urm[q];
			if( S[i] == P[q+1] )
				++q;
			if( q == m )
				{
					++nrsol;
					if( nrsol > MaxM-1 )
						continue;
					sol[nrsol] = i - m;
				}
		}
}

int main()
{
	fin.getline( P+1 , MaxN );
	fin.getline( S+1 , MaxN );
	fin.close();
	n = strlen(S+1);
	m = strlen(P+1);
	kmp();
	fout << nrsol << '\n';
	for( int i = 1 ; i <= nrsol && i < MaxM ; i++ )
		fout << sol[i] << ' ';
	fout << '\n';
	fout.close();
	return 0;
}