Cod sursa(job #777295)

Utilizator danalex97Dan H Alexandru danalex97 Data 11 august 2012 19:44:09
Problema Potrivirea sirurilor Scor 86
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 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 <queue>
#include <cstring>
using namespace std;

const int Nmax = 2000011;

char A[Nmax],B[Nmax];
int N,M,Sift[Nmax],Con;

queue< int > Q;

ifstream F("strmatch.in");
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()
{
	F.getline(A,Nmax,'\n'); N=strlen( A );
	F.getline(B,Nmax,'\n'); 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();
	
	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 ( int(Q.size()) < 1000 )
				Q.push( i-N );
			q = Sift[q];
		}
	}
	
	G<<Con<<'\n';
	while ( int(Q.size()) > 1 )
	{
		G<<Q.front()<<' ';
		Q.pop();
	}
	G<<Q.front()<<'\n';
}