Cod sursa(job #1699103)

Utilizator mihai995mihai995 mihai995 Data 6 mai 2016 05:42:45
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

const int N = 1 + 2e6;
typedef unsigned hash_t;

vector<int> sol;
char buff[N];

hash_t pwr(hash_t val, int n){
	hash_t ans = 1;
	for (; n; n >>= 1, val *= val)
		if ( n & 1 ) ans *= val;
	return ans;
}

hash_t compute(char* s, int n){
	hash_t val = 0;
	for (int i = 0; i != n; i++)
		val = (val << 5) - val + s[i];
	return val;
}

int main(){
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);

	cin >> buff;
	int n = strlen(buff);
	hash_t need = compute(buff, n);

	cin >> buff;
	hash_t val = compute(buff, n);

	if ( need == val ) sol.push_back(0);

	hash_t hist_adjust = pwr(31, n);
	for (int i = n; buff[i]; i++){
		val = (val << 5) - val + buff[i] - buff[i - n] * hist_adjust;
		if ( val == need ) sol.push_back(i - n + 1);
	}

	cout << sol.size() << '\n';
	if ( sol.size() > 1000 )
		sol.resize(1000);
	for (int x : sol)
		cout << x << ' ';
	cout << '\n';

	return 0;
}