Cod sursa(job #692160)

Utilizator the_snyper06FMI - ALexandru Mihai the_snyper06 Data 26 februarie 2012 14:20:19
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;

vector <int> sol;
char a[2000001], b[2000001];
const int MOD = 999983, baza = 'z' - '0';
int p;

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