Cod sursa(job #2391968)

Utilizator S_AndyAndrei S S_Andy Data 29 martie 2019 14:24:28
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <string>

using namespace std;


int sizeA, num;
int matches[1000];
char a[2000000], b[2000000];


bool Check_Match(int j) {
	for (int i = 0; i < sizeA; ++i) {
		if (a[i] != b[j++]) {
			return false;
		}
	}
	return true;
}

void Try_Match(int j) {
	if (Check_Match(j)) {
		if (num < 1000) {
			matches[num] = j;
		}
		++num;
	}
}

int main() {
	freopen("strmatch.in", "rt", stdin);
	freopen("strmatch.out", "wt", stdout);
	scanf("%s %s", a, b);
	sizeA = strlen(a);
	int n = strlen(b) - sizeA + 1;
	num = 0;
	long long s = 0, z = 0;
	for (int i = 0; i < sizeA; ++i) {
		s += int(a[i]);
		z += int(b[i]);
	}
	Try_Match(0);
	for (int i = 1, j = sizeA; i < n; ++i) {
		z = z - int(b[i - 1]) + int(b[j++]);
		if (z == s) {
			Try_Match(i);
		}
	}
	printf("%d\n", num);
	n = num < 1000 ? num : 1000;
	for (int i = 0; i < n; ++i) {
		printf("%d ", matches[i]);
	}
}