Cod sursa(job #692472)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 26 februarie 2012 16:22:07
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;

vector <int> sol;
char a[2000001], b[2000001];
const int MOD1 = 100021, MOD2 = 100007, baza = 'z' - '0';
int ha1, hb1, ha2, hb2;

int main(){
	freopen ("strmatch.in", "r", stdin), freopen("strmatch.out", "w", stdout);
	int i, j, n, m, bn1, bn2;
	scanf("%s\n%s", a, b);
	n = strlen(a), m = strlen(b);
	
	for (i = 0; i < n; i++)
		ha1 = (ha1 * baza + a[i] - '0') % MOD1,
		ha2 = (ha2 * baza + a[i] - '0') % MOD2,
		hb1 = (hb1 * baza + b[i] - '0') % MOD1,
		hb2 = (hb2 * baza + b[i] - '0') % MOD2;
	
	for (i = bn1 = bn2 = 1; i < n; i++) 
		bn1 = bn1 * baza % MOD1,
		bn2 = bn2 * baza % MOD2;
	
	for (i = 0; i < m - n + 1; i++){
		if (ha1 == hb1 && ha2 == hb2){
			for (j = 0; j < n && a[j] == b[i + j]; j++);
			if (j == n && sol.size() < 1000) sol.push_back(i);
		}
		
		hb1 = (((hb1 - bn1 * (b[i] - '0')) % MOD1 + MOD1) * baza + b[i + n] - '0') % MOD1;
		hb2 = (((hb2 - bn2 * (b[i] - '0')) % MOD2 + MOD2) * baza + b[i + n] - '0') % MOD2;
	}
	
	printf("%d\n", sol.size());
	for (i = 0; i < (int)sol.size(); i++)	printf("%d ", sol[i]);
	return 0;
}