Cod sursa(job #1114126)

Utilizator beldeabogdanBogdan Beldea beldeabogdan Data 21 februarie 2014 11:58:36
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define nmax 2000005
using namespace std;

int k,n;
char a[nmax],b[nmax];
int ha,hb[nmax];
const int p = 13,mod = 666013;
vector <int> r;
queue <int> q;
int sum,nr;

int putere(int b,int p) {
	if (p==1) return b;
	int put = putere(b,p/2);
	if (p%2==0) return put*put;
	else return put*put*b;
}

int hash(char x) {
	x = x-'A';
	if (q.size() > k) {
		sum -= q.front() * putere(p,k);
		q.pop();
	}
	sum *=p;
	sum %= mod;
	q.push(x);
	sum += p*x;
	sum %= mod;
	return sum;
}

bool check(int s) {
	int bun = true;
	for (int i=0;i<k;i++) if (a[i] != b[i+s]) bun = false; 
	if (bun) r.insert(r.begin(),s);
	return bun;
}

int main() {
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf("%s %s",a,b);
	k = strlen(a);
	n = strlen(b);
	for (int i=1;i<=n;i++) {
		hb[i] = hash(b[i]);
	}
	for (int i=1;i<=k;i++) ha = hash(k);
	for (int i=1;i<=n-k;i++) if (check(i)) nr++;
	printf("%d\n",nr);
	while (!r.empty()) {
		printf("%d ",r.back());
		r.pop_back();
	}
	return 0;
}