Cod sursa(job #584770)

Utilizator XbyteAvram Florin Xbyte Data 26 aprilie 2011 18:04:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<fstream>
#include<cstdio>

using namespace std;

const int MaxN = 2000005;
const int MaxP = 1000;
const char InFile[] = "strmatch.in";
const char OutFile[] = "strmatch.out";

int N,M,urm[MaxN],sol[MaxP+1];
char A[MaxN],B[MaxN];

void KMP()
{
	int i,q,k;
	urm[1] = 0;
	k = 0;
	for( q = 2 ; q <= M ; q++ )
		{
			while( k && B[q] != B[k+1] )
				k = urm[k];
			if( B[q] == B[k+1] )
				++k;
			urm[q] = k;
		}
	q = M+1;
	for( i = 1 ; i <= N ; i++ )
		{
			while( q && A[i] != B[q+1] )
				q = urm[q];
			if( B[q+1] == A[i] )
				++q;
			if( q == M )
				{
					++sol[0];
					if( sol[0] > MaxP )
						continue;
					sol[sol[0]] = i-M;
				}
		}
}

int main()
{
	ifstream fin ( InFile );
	ofstream fout ( OutFile );
	fin.getline(B+1,MaxN);
	fin.getline(A+1,MaxN);
	fin.close();
	N = strlen(A+1);
	M = strlen(B+1);
	KMP();
	fout << sol[0] << '\n';
	for( int i = 1 ; i <= sol[0] && i <= MaxP ; i++ )
		fout << sol[i] << ' ';
	fout << '\n';
	fout.close();
	return 0;
}