Cod sursa(job #3141818)

Utilizator daristyleBejan Darius-Ramon daristyle Data 16 iulie 2023 20:33:55
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.01 kb
#include <fstream>

using namespace std;
ifstream fin("probleme.in");
ofstream fout("probleme.out");

int lgpow(int b, int e, int mod){
	int p = 1;
	while(e){
		if(e & 1)
			p = (long long) p * b % mod;
		b = (long long) b * b % mod;
		e >>= 1;
	}

	return p;
}

struct Hash{
		int value, mod, base, base_power;

		void init(int _mod, int _base, int pattern_length){
			value = 0;
			mod = _mod;
			base = _base;
			base_power = lgpow(base, pattern_length - 1, mod);
		}

		void add(char ch){
			value = ((long long) value * base % mod + ch - 'A');
			if(value >= mod)
				value -= mod;

		}

		void remove(char ch){
			value = value - ((long long) (ch - 'A') * base_power % mod);
			if(value < 0)
				value += mod;
		}

		int compute(char *s, int slen){
			int val = 0;
			for(int i = 0; i < slen; ++i){
				val = ((long long) val * base % mod + s[i] - 'A');
				if(val >= mod)
					val -= mod;
			}

			return val;
		}
};

const int STRLEN_MAX = 2e6;
const int APP_MAX = 1e3;

char s[STRLEN_MAX + 1], pattern[STRLEN_MAX + 1];
int v[APP_MAX];

int length(char *s){
	int len = 0;

	while(s[len]) ++len;

	return len;
}

int GetApparitions(char *s, char *pattern){
	int ret = 0;
	const int len = length(pattern);
	const int HASHES = 3;
	const int BASE = 256;
	const int mod[] = {(int) 1e9 + 7, (int) 1e9 + 9, (int) 1e9 + 21};
	Hash h[HASHES];
	for(int i = 0; i < HASHES; ++i)
		h[i].init(mod[i], BASE, len);
	int pattern_hash[HASHES];
	for(int i = 0; i < HASHES; ++i){
		pattern_hash[i] = h[i].compute(pattern, len);
		h[i].value = h[i].compute(s, len - 1);
	}

	int j = len - 1;
	while(s[j]){
		int found = 0;
		for(int i = 0; i < HASHES; ++i){
			h[i].add(s[j]);
			if(h[i].value == pattern_hash[i])
				++found;
			h[i].remove(s[j - len + 1]);
		}

		if(found == HASHES)
			v[ret++] = j - len + 1;

		++j;
	}

	return ret;
}

int main(){
	fin >> pattern >> s;

	int apparitons = GetApparitions(s, pattern);

	fout << apparitons << '\n';
	for(int i = 0; i < apparitons; ++i)
		fout << v[i] << ' ';
	fout.put('\n');

	fin.close();
	fout.close();
	return 0;
}