Cod sursa(job #777306)

Utilizator danalex97Dan H Alexandru danalex97 Data 11 august 2012 20:00:41
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
// Algoritmul KMP are complexitatea liniara O(N+M) si ajuta
// la potrivirea unui sir peste altul. Pentru a afla locul 
// potrivirilor putem face sirul de prefixe ale primului sir.
// Sirul de prefixe consta in aflarea la trimiterea de la sfarsitul
// sirului A pe pozitia de unde am putea continua algoritmul.
// Viteza cu care se face sirul de prefixe este relativ mare
// deoarece o siftare spre stanga se produce in maxim 2 pasi.
// Exemplu:
// A= ABABBABBA
// S= 001201201 // sir de prefixe
// Siftarea spre stanga se face cu ajutorul variabilei q:
// variabila q creste nu creste pana cand nu se gaseste un cracter 
// identic cu primul, apoi q creste daca A[q]=A[i] , iar daca 
// A[q]!=A[i] atunci il siftam pe q la stanga.
// Dupa finalul parcurgerii sunt necesare doar elementele 
// din vectorul de prefixe.

#include <fstream>
#include <cstring>
using namespace std;

const int Nmax = 2000011;

char A[Nmax],B[Nmax];

int N,M,Sift[Nmax];
int Q[1011],Con;

ofstream G("strmatch.out");

void Make_sift()
{
	int q=0;
	
	for (int i=2;i<=N;++i )
	{
		while ( q && A[i]!=A[q+1] ) q = Sift[q];
		if ( A[i]==A[q+1] ) ++q;
		Sift[i] = q;
	}
}

int main()
{
	freopen("strmatch.in","r",stdin);
	
	fgets(A,sizeof(A),stdin); N=strlen( A );
	fgets(B,sizeof(B),stdin); M=strlen( B );
	
	for (int i=N;i;--i) A[i]=A[i-1];
	for (int i=M;i;--i) B[i]=B[i-1];
	A[0]=B[0]=0;
	
	Make_sift();
	
	if ( N>M ) G<<"0\n";
	
	int q=0;
	for (int i=1;i<=M;++i)
	{
		while ( q && B[i]!=A[q+1] ) q = Sift[q];
		if ( B[i]==A[q+1] ) ++q;
		
		if ( q==N )
		{
			++Con;
			if ( Con <= 1000 )
				Q[Con]=i-N;
			q = Sift[q];
		}
	}
	
	G<<Con<<'\n';
	for (int i=1;i<=min(Con,1000);++i)
		G<<Q[i]<<' ';
	G<<'\n';
}