Cod sursa(job #692170)

Utilizator the_snyper06FMI - ALexandru Mihai the_snyper06 Data 26 februarie 2012 14:31:03
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<cstdio>
#include<cstring>
#include<vector>
#include<deque>

using namespace std;
char a[2000001], b[2000001];
int na, nb, nr;
vector <int> L;

int main() {
	int i, n, m, k;
	
	freopen("strmatch.in", "r", stdin), freopen("strmatch.out", "w", stdout);
	scanf("%s %s", a, b);
	n = strlen(a), m = strlen(b);
	
	for(i = 0; i < n; i++) na = na + (a[i] - '0'), nb = nb + (b[i] - '0');
	for(i = 0; i < m - n; i++) {
		if(nb == na) {
			for (k = 0; k < n && a[k] == b[k + i]; k++);
			if (k == n) nr++, L.push_back(i);
		}
		
		nb = nb - (b[i] - '0');		
		nb = nb + (b[i + n] - '0');
	}
	
	printf("%d\n", nr); 
	for(i = 0; i < nr && i < 1000; i++) printf("%d ", L[i]);
	
	return 0;
}