Cod sursa(job #2293992)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 1 decembrie 2018 19:36:42
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 5.9 kb
#include <bits/stdc++.h>
using namespace std;

class ModInt {

protected:

	inline long long logPower(long long x, long long n) {
		long long ans = 1, mod = n + 2;
		for (; n; n >>= 1) {
			if (n & 1) { 
				ans = ans * x % mod; }
			if (n | 1) { 
				x = x * x % mod; } }
		return ans; }

public:
	
	long long x, mod;

	ModInt() : 
		x(0), mod(1000000007) {}
	ModInt(const ModInt &other) : 
		x(other.x), mod(other.mod) {}
	ModInt(const long long _x) :
		x(_x), mod(1000000007) {
		if (x < 0 or x >= mod) {		
			x = (x % mod + mod) % mod; } }
	ModInt(long long _x, long long _mod) :
		x(_x), mod(_mod) {
		if (x < 0 or x >= mod) {
			x = (x % mod + mod) % mod; } }
	
// type I

	inline ModInt operator +(const ModInt other) {
		return ModInt((x + other.x) % mod, mod); }
	inline ModInt operator -(const ModInt other) {
		return ModInt((x - other.x + mod) % mod, mod); }
	inline ModInt operator *(const ModInt other) {
		return ModInt(1LL * x * other.x % mod, mod); }
	inline ModInt operator /(const ModInt other) {
		return ModInt(1LL * x * logPower(other.x, mod - 2) % mod, mod); }
	
	inline ModInt operator +=(const ModInt other) {
		x = (x + other.x) % mod; return *this; }
	inline ModInt operator -=(const ModInt other) {
		x = (x - other.x + mod) % mod; return *this; }
	inline ModInt operator *=(const ModInt other) {
		x = x * other.x % mod; return *this; }
	inline ModInt operator /=(const ModInt other) {
		x = x * logPower(other.x, mod - 2) % mod; return *this; }

	inline bool operator ==(const ModInt other) {
		return x == other.x and mod == other.mod; }

// type II
	
	inline ModInt operator +(const long long other) {
		return *this + ModInt(other); }
	inline ModInt operator -(const long long other) {
		return *this - ModInt(other); }
	inline ModInt operator *(const long long other) {
		return *this * ModInt(other); }
	inline ModInt operator /(const long long other) {
		return *this / ModInt(other); }
	
	inline ModInt operator +=(const long long other) {
		return *this = *this + ModInt(other); }
	inline ModInt operator -=(const long long other) {
		return *this = *this - ModInt(other); }
	inline ModInt operator *=(const long long other) {
		return *this = *this * ModInt(other); }
	inline ModInt operator /=(const long long other) {
		return *this = *this / ModInt(other); }

	inline bool operator ==(const long long other) {
		return x == other; }
};

class ModPair : protected ModInt {

public:

	long long x, y, mod1, mod2;
	
	ModPair() :
		x(0), y(0), mod1(1000000007), mod2(1000000009) {}
	ModPair(const ModPair &other) :
		x(other.x), y(other.y), mod1(other.mod1), mod2(other.mod2) {}
	ModPair(const long long _x, const long long _y) :
		x(_x), y(_y), mod1(1000000007), mod2(1000000009) {
		if (x < 0 or x >= mod1) {
			x = (x % mod1 + mod1) % mod1; }
		if (y < 0 or y >= mod2) {
			y = (y % mod2 + mod2) % mod2; } }
	ModPair(const long long _x, const long long _y, const long long _mod1, const long long _mod2) :
		x(_x), y(_y), mod1(_mod1), mod2(_mod2) {
		if (x < 0 or x >= mod1) {
			x = (x % mod1 + mod1) % mod1; }
		if (y < 0 or y >= mod2) {
			y = (y % mod2 + mod2) % mod2; } }

// type I

	inline ModPair operator +(const ModPair other) {
		return ModPair((x + other.x) % mod1, (y + other.y) % mod2, mod1, mod2); }
	inline ModPair operator -(const ModPair other) {
		return ModPair((x - other.x + mod1) % mod1, (y - other.y + mod2) % mod2, mod1, mod2); }
	inline ModPair operator *(const ModPair other) {
		return ModPair(x * other.x % mod1, y * other.y % mod2, mod1, mod2); }
	inline ModPair operator /(const ModPair other) {
		return ModPair(x * logPower(other.x, mod1 - 2) % mod1, y * logPower(other.y, mod2 - 2) % mod2, mod1, mod2); }
	
	inline ModPair operator +=(const ModPair other) {
		x = (x + other.x) % mod1; y = (y + other.y) % mod2; return *this; }
	inline ModPair operator -=(const ModPair other) {
		x = (x - other.x + mod1) % mod1; y = (y - other.y + mod2) % mod2; return *this; }
	inline ModPair operator *=(const ModPair other) {
		x = x * other.x % mod1; y = y * other.y % mod2; return *this; }
	inline ModPair operator /=(const ModPair other) {
		x = x + logPower(other.x, mod1 - 2) % mod1; y = y * logPower(other.y, mod2 - 2) % mod2; return *this; }
	
	inline bool operator ==(const ModPair other) {
		return x == other.x and y == other.y and mod1 == other.mod1 and mod2 == other.mod2; }

// type II

	inline ModPair operator +(const long long other) {
		return *this + ModPair(other, other, mod1, mod2); }
	inline ModPair operator -(const long long other) {
		return *this - ModPair(other, other, mod1, mod2); }
	inline ModPair operator *(const long long other) {
		return *this * ModPair(other, other, mod1, mod2); }
	inline ModPair operator /(const long long other) {
		return *this / ModPair(other, other, mod1, mod2); }
	
	inline ModPair operator +=(const long long other) {
		return *this = *this + ModPair(other, other, mod1, mod2); }
	inline ModPair operator -=(const long long other) {
		return *this = *this - ModPair(other, other, mod1, mod2); }
	inline ModPair operator *=(const long long other) {
		return *this = *this * ModPair(other, other, mod1, mod2); }
	inline ModPair operator /=(const long long other) {
		return *this = *this / ModPair(other, other, mod1, mod2); }

	inline bool operator ==(const long long other) {
		return x == other and y == other; }
};

const int DIM = 2000005;

char str1[DIM], str2[DIM]; 

int main(void) {
	freopen("strmatch.in", "r", stdin); 
	freopen("strmatch.out", "w", stdout);
	cin >> (str1 + 1) >> (str2 + 1);
	int n = (int) strlen(str1 + 1), m = (int) strlen(str2 + 1);
	ModPair hsh, pwr(1, 1), hsh2; vector<int> sol; int ans = 0; 
	for (int i = 1; i <= n; ++i) {
		hsh = hsh * 26 + str1[i]; }
	for (int i = 1; i <= m; ++i) {
		if (i <= n) {
			hsh2 = hsh2 * 26 + str2[i]; pwr *= 26; }
		else {
			hsh2 = hsh2 * 26 - pwr * str2[i - n] + str2[i]; }
		if (i >= n and hsh2 == hsh) {
			++ans;
			if (sol.size() < 1000) {
				sol.push_back(i - n); } } }
	cout << ans << endl;
	for (int x : sol) {
		cout << x << " "; }
	return 0; }