Cod sursa(job #3256077)

Utilizator adimiclaus15Miclaus Adrian Stefan adimiclaus15 Data 13 noiembrie 2024 11:07:48
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <vector>
using ll = long long;
#define int ll

using namespace std;

const int mod = 1e9 + 7, baza = 65;

vector <int> va;

int lgput(int n, int e) {
	if (e == 0)
		return 1;
	int aux = lgput(n, e / 2);
	if (e % 2) return ((aux * aux) % mod) * n % mod;
	else return (aux * aux) % mod;
}

int pozitie(char c) {
	if ('A' <= c && c <= 'Z')
		return c - 65 + 1;
	if ('a' <= c && c <= 'z')
		return c - 97 + 1 + 26;
	if ('0' <= c && c <= '9')
		return c - 48 + 26 * 2 + 1;
}

struct HASH {
	int init(string s, int r) {
		int hash = 0, pb = 1;
		for (int i = 0; i < r; i++) {
			hash += pb * pozitie(s[i]);
			hash %= mod;
			pb *= baza;
			pb %= mod;
		}
		return hash;
	}
	int sequence(int remove, int add, string s, int lh, int lg) {
        lh -= pozitie(s[remove]);
		lh = (lh * lgput(baza, mod - 2)) % mod;
		lh = (lh + (pozitie(s[add]) * lgput(baza, lg)) % mod) % mod;
		return lh;
	}
};

signed main() {
	string a, b;
	cin >> a >> b;
	HASH hash;
	int ha = hash.init(a, a.size()), hc = hash.init(b, a.size()), ans = 0;
	for (int i = a.size(); i < b.size(); i++) {
		if (ha == hc)
			ans++, va.push_back(i - a.size());
		hc = hash.sequence(i - a.size(), i, b, hc, a.size() - 1);
	}
	if (ha == hc)
		ans++, va.push_back(b.size() - 1);
	cout << ans << '\n';
	for (auto x : va)
		cout << x << ' ';
}