Cod sursa(job #1347795)

Utilizator kassay_akosKassay Akos kassay_akos Data 19 februarie 2015 11:26:33
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <stdio.h>

char A[100],B[100],sab[100],megoldasok[100];
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;
	}
}


void 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(int i=0; (A[i] >='a' && A[i]<='z') || (A[i] >='A' && A[i]<='Z') || (A[i] >='0' && A[i]<='9');++a,++i);
	for(int i=0; (B[i] >='a' && B[i]<='z') || (B[i] >='A' && B[i]<='Z') || (B[i] >='0' && B[i]<='9');++b,++i);

	// 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");

}