Cod sursa(job #3256095)

Utilizator Sebi_RipaSebastian Ripa Sebi_Ripa Data 13 noiembrie 2024 12:54:28
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <vector>
using ll = long long;
#define int ll

using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

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;
}

const int put = lgput(baza, mod - 2);
int put2;

int pozitie(char c) {
	if ('A' <= c && c <= 'Z')
		return c - 65 + 1;
	if ('a' <= c && c <= 'z')
		return c - 97 + 1 + 26;
	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) {
		lh -= pozitie(s[remove]);
		lh = (lh * put) % mod;
		lh = (lh + (pozitie(s[add]) * put2) % 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;
	put2 = lgput(baza, a.size() - 1);
	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);
	}
	if (ha == hc)
		ans++, va.push_back(b.size() - 1);
	cout << ans << '\n';
	int sz = va.size();
	for (int i = 0; i < min(sz, (ll)1001); i++)
		cout << va[i] << ' ';
}