Cod sursa(job #3238115)

Utilizator elisa.ipateElisa Ipate elisa.ipate Data 19 iulie 2024 22:45:02
Problema Potrivirea sirurilor Scor 8
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>

using namespace std;
 
#define int long long
#define base1 37
#define base2 41
const int mod1 = 1e9 + 7;
const int mod2 = 1e9 + 9;
#define nmax 2000001

struct info{
	int a, b;
	bool operator == (const info&x ) const {
		if( x.a == a && x.b == b )
			return true;
		return false;
	};
};

string a, b;

info v[nmax], zero = {0, 0};

int to_number( char ch ) {
	if( 'a' <= ch && ch <= 'z' )
		return ch - 'a';
	return ch - 'A' + 27;
}

info f( int i, int j ) {
	info x = zero;
	int p1 = 1, p2 = 1, k;
	for( k = i; k <= j; k++ ) {
		x.a = (x.a + (to_number(b[k])) * p1) % mod1;
		x.b = (x.b + (to_number(b[k])) * p2) % mod2;
		p1 = (p1 * base1) % mod1;
		p2 = (p2 * base2) % mod2;
	}
	return x;
}

signed main() {
	int cnt = 0, i;
	info rez;
	ifstream cin("strmatch.in");
	ofstream cout("strmatch.out");
	cin >> a >> b;
	for( i = a.size() - 1; i < b.size(); i++ )
		v[i] = f(i - a.size() + 1, i);
	
	for( i = 0; i < a.size(); i++ )
		b[i] = a[i];
	rez = f(0, a.size() - 1);
	for( i = a.size() - 1; i < b.size(); i++ ) {
		if( v[i] == rez )
			cnt++;
	}
	cout << cnt << "\n";
	
	for( i = a.size() - 1; i < b.size(); i++ ) {
		if( v[i] == rez )
			cout << i - a.size() + 2 << " ";
	}
	//cout << "\n" << rez.a << " " << rez.b << "\n";
	return 0;
}