Cod sursa(job #1347814)

Utilizator kassay_akosKassay Akos kassay_akos Data 19 februarie 2015 11:39:04
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <stdio.h>

char A[2000005], B[2000005];
int  sab[2000005], megoldasok[2014];
int a=0, b=0;	

void createFiniteStates(){
	int jo = 0;
	sab[1] = 0;
	for (int i = 2; i<=a; ++i){
		while (jo != 0 && A[jo+1] != A[i])
			jo = sab[jo];
		if (A[jo+1] == A[i])
			++jo;
		sab[i]=jo;
	}
}


int main(){

	freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
	
	//beolvasom a 2 karakterlancot
	fgets(A, sizeof(A), stdin);
    fgets(B, sizeof(B), stdin);

	//megszamolom hany karacterbol allnak
	for(a=0; (A[a] >='a' && A[a]<='z') || (A[a] >='A' && A[a]<='Z') || (A[a] >='0' && A[a]<='9');++a);
	for(b=0; (B[b] >='a' && B[b]<='z') || (B[b] >='A' && B[b]<='Z') || (B[b] >='0' && B[b]<='9');++b);

	// eltoom az egeszet 1-el jobbra hogy A[1] legyen az elso karakter 
	for(int i =a; i>0 ; A[i] = A[i-1],--i); A[0] = ' ';
	for(int i =b; i>0 ; B[i] = B[i-1],--i); B[0] = ' ';

	// eloallitom a sablont
	createFiniteStates();

	int n = 0;												// n a megoldasok szama
	int aa = 0;												//aa-val megyek a sab tomben

	for (int i = 1; i<=b; ++i) {
		
		while (aa != 0 && A[aa+1] != B[i] )
			aa = sab[aa];
		if (A[aa+1] == B[i] )
			aa++;
		if (aa == a )
		{
			aa = sab[a];
            ++n;
            if (n <= 1000)
                megoldasok[n] = i-a;  
		}
	}

	printf("%d\n", n);
    for (int i = 1; i <= n; ++i)
        printf("%d ", megoldasok[i]);
    printf("\n");

	return 0;
}