Cod sursa(job #2391953)

Utilizator S_AndyAndrei S S_Andy Data 29 martie 2019 13:56:29
Problema Potrivirea sirurilor Scor 66
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <vector>
#include <string>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int sizeA, num;
int *matches;
string a, b;


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)) {
		matches[num++] = j;
	}
}

int main() {
	getline(fin, a);
	getline(fin, b);
	sizeA = a.size();
	int n = b.size() - sizeA + 1;
	num = 0;
	matches = new int[n];
	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);
		}
	}
	fout << num << "\n";
	n = num < 1000 ? num : 1000;
	for (int i = 0; i < n; ++i) {
		fout << matches[i] << " ";
	}
}