Cod sursa(job #3251930)

Utilizator luc3lexaAlexandrescu Luca luc3lexa Data 27 octombrie 2024 20:04:55
Problema Potrivirea sirurilor Scor 78
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>
using namespace std;

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

const int base = 127;
const int nmax = 2e6+10;
const int MOD = 1e9+7;

string s1,s2;

vector<long long int> hash_(nmax,0),base_power(nmax,0);
vector<int> ans;
long long n,m,s2_hash,ans_value;

void precalculations(){

	base_power[0] = 1;
	for(int i = 1; i <=nmax; i++){
		base_power[i] = (base_power[i-1]*base)%MOD;
	}
	
	s2_hash = 0;
	for(int i = 0; i <m; i++){
		s2_hash *= base;
		s2_hash += s2[i]-'0';
		s2_hash %= MOD;
	}
	
	for(int i = 1; i < n; i++){
		hash_[i+1] = hash_[i];
		
		hash_[i+1] *= base;
		hash_[i+1] += s1[i]-'0';
		hash_[i+1] %= MOD;
	}
}

void solve(){
	for(int i = m; i <=n; i++){
		long long int hash_dr = hash_[i];
		long long int hash_st = hash_[i-m];
		hash_st = (hash_st * base_power[m])%MOD;
		
		long long int hash_aux = (hash_dr-hash_st + MOD)%MOD;
		
		if(hash_aux == s2_hash){
			ans_value++;
			if(ans_value <= 1000){
				ans.push_back(i-m);
			}
		}
	}
}

int main(){
	fin >> s2 >> s1;
	n = (int) s1.length();
	m = (int) s2.length();
	
	precalculations();
	solve();
	
	fout << ans_value << '\n';
	for(auto x : ans){fout << x << " ";}
	return 0;
}