Cod sursa(job #3363205)

Utilizator CorvinJudge0Corvin Judge CorvinJudge0 Data 14 august 2026 12:42:56
Problema Potrivirea sirurilor Scor 26
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

#ifdef LOCAL
#define fin cin
#define fout cout
#else
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#endif

const long long B=67;
const int MOD=1e9+7, NMAX=2e6;

long long hash_b[NMAX];
long long puteri_B[NMAX];
vector<int> rasp;

int my_hash(char ch, int poz) {
	if (ch >= '0' && ch <= '9') return ((ch - '0' + 1) * puteri_B[poz]) % MOD;
	if (ch >= 'a' && ch <= 'z') return ((ch - 'a' + 11) * puteri_B[poz]) % MOD;
	return ((ch - 'A' + 37) * puteri_B[poz]) % MOD;
}

long long fastpow(int x, int y) {
	if (y == 0) return 1;
	long long jum = fastpow(x, y / 2);
	if (y % 2 == 0) return (jum * jum) % MOD;
	return (((jum * jum) % MOD) * x) % MOD;
}

int main() {
	string a, b;
	int n=0;
	long long hash_a=0;
	fin >> a >> b;
	puteri_B[0] = 1;
	for (int i=1; i<NMAX; i++) puteri_B[i] = (puteri_B[i - 1] * B) % MOD;
	for (int i=0; i<a.size(); i++) {
		hash_a = (hash_a + my_hash(a[i], i)) % MOD;
	}
	hash_b[0] = my_hash(b[0], 0);
	for (int i=1; i<b.size(); i++)
		hash_b[i] = (hash_b[i - 1] + my_hash(b[i], i)) % MOD;
	if (hash_b[a.size() - 1] == hash_a) {
		n++;
		rasp.push_back(0);
	}
	for (int i=0; i<b.size()-a.size(); i++)
		if ((((hash_b[i + a.size()] - hash_b[i] + MOD) % MOD) * fastpow(puteri_B[i + 1], MOD - 2)) % MOD == hash_a) {
			n++;
			if (n <= 1000) rasp.push_back(i + 1);
		}
	fout << n << '\n';
	for (auto poz:rasp) fout << poz << ' ';
}