Cod sursa(job #1142200)

Utilizator bogdanrusRus Bogdan bogdanrus Data 13 martie 2014 16:36:18
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
// Compilare g++ sursa.cpp -o binar
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

#define NMax 2000000

//Complexity = O(N+M)

int T[NMax], R[NMax], Na, Nb, aparitii;
char A[NMax], B[NMax];

//A - sirul cautat
//B - sirul in care se cauta aparitiile lui A

void calculT (void) {
int pos, index;
	T[0]=-1;
	T[1]=0;
	pos = 2; //pentru parcurgerea lui T
	index = 0; //pentru parcurgerea lui A
	
	while (pos < Na) {
		if(A[pos-1]==A[index]) {
			++index;
			T[pos]=index;
			++pos;
		} else 
			if (index>0)
				index=T[index];
			else {
				T[pos]=0;
				++pos;
			}	
	}
}


void potrivireSiruri (void) {
int m,i;
i=0;
m=0;
	while (m+i<Nb) {
		if (B[m+i]==A[i])
			if (i==Na-1) {
				R[aparitii]=m;
				++aparitii;
				++m;
				i=0;
			}
			else 
				++i;
		else {
			m=m+i-T[i];
			if (T[i]>-1)
				i = T[i];
			else
				i = 0;
		}	
	}
}


void printResult (void) {
int i;
	printf("%d\n",aparitii);
	for (i=0; i<aparitii; ++i)
		printf("%d ",R[i]);
}

int main (void) {
	
	int i;
    freopen("strmatch.in", "rt", stdin);
    freopen("strmatch.out", "wt", stdout);
    scanf("%s %s", A, B);
    
    Na = strlen(A);
    Nb = strlen(B);
	
	aparitii=0;
	
	calculT();
	potrivireSiruri();
	printResult();

return 0;
}