Cod sursa(job #3192449)

Utilizator verde.cristian2005Verde Flaviu-Cristian verde.cristian2005 Data 12 ianuarie 2024 17:07:03
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
using namespace std;

#ifndef HOME
	ifstream in("strmatch.in");
	ofstream out("strmatch.out");
	#define cin in
	#define cout out
#endif

const int baza = 63, MOD = 1e9 + 7;
int pref[2000001];
string a, b;

int cifra(char c)
{
	if('A' <= c && c <= 'Z')
		return c - 'A' + 1;
	if('a' <= c && c <= 'z')
		return c - 'a' + 27;
	return c - '0' + 53;
}

int put = 1;
int afis[1001];

int codificare(int i, int j)
{
	if(i == 0)
		return pref[j];
	return (pref[j] - 1LL * pref[i - 1] * put % MOD + MOD) % MOD;
}

int main()
{
#ifdef HOME
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif // HOME
	int cod = 0;
	cin >> a >> b;
	for(int i = 0; i < a.size(); i++)
		cod = (1LL * cod * baza + cifra(a[i])) % MOD;
	for(int i = 0; i < a.size(); i++)
		put = 1LL * put * baza % MOD;
	pref[0] = cifra(b[0]);
	for(int i = 1; i < b.size(); i++)
		pref[i] = (1LL * pref[i - 1] * baza + cifra(b[i])) % MOD;
	int cnt = 0;
	for(int i = 0; i + a.size() - 1 < b.size(); i++)
		if(cod == codificare(i, i + a.size() - 1))
		{
			cnt++;
			if(cnt <= 1000)
				afis[cnt] = i;
		}
	cout << cnt << '\n';
	for(int i = 1; i <= min(cnt, 1000); i++)
		cout << afis[i] << " ";
    return 0;
}