Cod sursa(job #777308)

Utilizator danalex97Dan H Alexandru danalex97 Data 11 august 2012 20:02:29
Problema Potrivirea sirurilor Scor 86
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 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); 
	fgets(B,sizeof(B),stdin); 
	
	for (; (A[N] >= 'A' && A[N] <= 'Z') || (A[N] >= 'a' && A[N] <= 'z') 
			|| (A[N] >= '0' && A[N] <= '9'); ++N);
	for (; (B[M] >= 'A' && B[M] <= 'Z') || (B[M] >= 'a' && B[M] <= 'z')
			|| (B[M] >= '0' && B[M] <= '9'); ++M);
	
	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';
}