Cod sursa(job #2391607)

Utilizator S_AndyAndrei S S_Andy Data 29 martie 2019 04:05:40
Problema Potrivirea sirurilor Scor 78
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <vector>
#include <string>

using namespace std;

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

int sizeA;
vector<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.push_back(j);
	}
}

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