Cod sursa(job #2019065)

Utilizator bcrisBianca Cristina bcris Data 6 septembrie 2017 20:39:51
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include <stdio.h>
#include <vector>
#include <cstdio>
#include <string.h>

using namespace std;

#define NMAX 2000005
#define min(a, b) ((a < b) ? a : b)

int M, N;
int table[NMAX], solutions[1024];
char A[NMAX], B[NMAX];




void make_prefix() {
	int i, j = 0;
	

	for (i = 2, table[1] = 0; i <= M; ++i) {
		while (j && A[j+1] != A[i])
			j = table[j];
		if (A[j+1] == A[i])
			++j;
		table[i] = j;
	}
}

void search() {
	

	// while(m + i <= N) {
	// 	if (A[i] == B[m + i]) {
	// 		i++;
	// 		if (i == M) {
	// 			solutions[n_sol] = m;
	// 			n_sol++;
	// 			m = m + i - table[i-1];
	// 			i = table[i-1];
	// 		}
	// 	} else {
	// 		if (i > 0) {
	// 			if (table[i-1] > 0) {
	// 				m = m + i - table[i-1];
	// 				i = table[i];
	// 			} else {
	// 				m = m + i + 1 - table[i-1];
	// 				i = 0;
	// 			}	
	// 		} else {
	// 			m = m + i + 1;
	// 			i = 0;
	// 		}	
	// 	}
	// }
}

int main()
{
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	int i, j=0, n_sol=0;
	
	fgets(A, sizeof(A), stdin);
    fgets(B, sizeof(B), stdin);
	for (; (A[M] >= 'A' && A[M] <= 'Z') || (A[M] >= 'a' && A[M] <= 'z') 
            || (A[M] >= '0' && A[M] <= '9'); ++M)
		;
    for (; (B[N] >= 'A' && B[N] <= 'Z') || (B[N] >= 'a' && B[N] <= 'z')
            || (B[N] >= '0' && B[N] <= '9'); ++N)
    	;
    for (i = M; i; --i) A[i] = A[i-1]; A[0] = ' ';
    for (i = N; i; --i) B[i] = B[i-1]; B[0] = ' ';  

	make_prefix();
	//search();
	

	for (int i = 1; i <= N; ++i) {
		while (j && A[j+1] != B[i])
			j = table[j];
		if (A[j+1] == B[i])
			++j;
		if (j == M) {
			j = table[M];
			n_sol++;
			if (n_sol < 1000) {
				solutions[n_sol] = i - M;
			}
		}
	}

	printf("%d\n", n_sol);
	for (int i = 1; i <= min(1000, n_sol); i++) {
		printf("%d ", solutions[i]);
	}


	return 0;
}