Cod sursa(job #1174135)

Utilizator DuxarFII-Stefan-Negrus Duxar Data 22 aprilie 2014 01:01:37
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include <vector>
#include <cstdio>
#include <climits>
#include <algorithm>
#include <string>
#include <iostream>
#include <fstream>

using namespace std;

#define ONLINE_JUDGE

#define MOD1 100007
#define MOD2 100021
#define base 73

#define pb push_back
#define ENTER fprintf(output, "\n");
#define OKK fprintf(output, "ok!\n");
#define all(V) V.begin(), V.end()
#define allr(V) V.rbegin(), V.rend()
#define LL long long

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;

LL hashA1, hashA2, hashB1, hashB2;
string A, B;
LL fact1 = 1, fact2 = 1;
vi ans;

int main() {
#ifdef ONLINE_JUDGE
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
#else
	freopen("input.txt", "r", stdin);
#endif
	
	int lgA, lgB, i;
	
	cin >> A >> B;
	lgA = A.length();
	lgB = B.length();
	
	if (lgA > lgB) {
		cout << 0;
		return 0;
	}
	
	hashA1 = hashA2 = A[0];
	hashB1 = hashB2 = B[0];
	
	for (i = 1; i < lgA; ++i) {
		hashA1 = hashA1 * base + A[i]; hashA1 %= MOD1;
		hashA2 = hashA2 * base + A[i]; hashA2 %= MOD2;
		
		hashB1 = hashB1 * base + B[i]; hashB1 %= MOD1;
		hashB2 = hashB2 * base + B[i]; hashB2 %= MOD2;
		
		fact1 *= base; fact1 %= MOD1;
		fact2 *= base; fact2 %= MOD2;
	}
	
	if (hashA1 == hashB1 && hashA2 == hashB2) {
		ans.pb(i - lgA);
//cout << "okk\n";
	}
	//cout << A << '\n' << B; 
	for (i = lgA; i < lgB; ++i) {
		//cout << hashA1 << " ---- " << hashA2 << '\n';
		//cout << hashB1 << " ---- " << hashB2 << '\n';
		hashB1 = ((hashB1 + MOD1 - (B[i - lgA] * fact1) % MOD1)) * base + B[i];
		hashB1 %= MOD1;
		hashB2 = ((hashB2 + MOD2 - (B[i - lgA] * fact2) % MOD2)) * base + B[i];
		hashB2 %= MOD2;
		//cout << hashB1 << " ---- " << hashB2 << '\n';
		if (hashA1 == hashB1 && hashA2 == hashB2) {
			ans.pb(i - lgA + 1);
			if (ans.size() == 1000) {
				break;
			}
		}
	}
	
	cout << ans.size() << '\n';
	for (auto x: ans) {
		cout << x << ' ';
	}
	
	return 0;
}