Cod sursa(job #3291735)

Utilizator CosminaneBoac Mihai Cosmin Cosminane Data 5 aprilie 2025 14:10:59
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
const long long MOD = ( 1ll << 60 ) - 1;
long long p62;
long long add_dr( long long x, int a ){
	x = ( x * 62 + a ) % MOD;
	return x;
}
long long rem_st(long long x, int a){
	x = ( x - p62 * a % MOD + MOD ) % MOD;
	return x;
}
int trans(char c){
	if( 'a' <= c && c <= 'z' ){
		return c - 'a' + 1;
	}
	if( 'A' <= c && c <= 'Z' ){
		return c - 'A' + 27;
	}
	return c - '0' + 53;
}
vector <long long> ras;
int main(){
	int i, n;
	long long x, y;
	string s;
	ifstream fin( "strmatch.in" );
	ofstream fout( "strmatch.out" );
	fin >> s;
	x = 0;
	p62 = 1;
	for( i = 0; i < s.size(); i++ ){
		x = add_dr( x, trans( s[i] ) );
		p62 = p62 * 62 % MOD;
	}
	n = s.size();
	//cout << x << ' ' << n << '\n';
	fin >> s;
	y = 0;
	for( i = 0; i < s.size(); i++ ){
		y = add_dr( y, trans( s[i] ) );
		if( i >= n ){
			y = rem_st( y, trans( s[i - n] ) );
		}
		//cout << y << '\n';
		if( x == y ){
			ras.push_back( i - n + 1 );
		}
	}
	fout << ras.size() << '\n';
	for( i = 0; i < min( ( int ) ras.size(), 1000 ); i++ ){
		fout << ras[i] << ' ';
	}
	return 0;
}