Cod sursa(job #812693)

Utilizator IoannaPandele Ioana Ioanna Data 14 noiembrie 2012 11:26:19
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include<fstream>
#include<string>
#include<vector>
#define mod1 666001
#define mod2 1000007
using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");

string a,b;
vector <int> poz;
int cod1,cod2,h1,h2,nr;

void scan()
{
	in>>a;
	in>>b;
}

void code(int &cod1,int &cod2)
{
	int l;
	int k1=0,k2=0;
	l=a.size()-1;
	for (int i=0;i<=l;i++)
	{
		k1=((k1*26)%mod1+a[i]-'A')%mod1;
		k2=((k2*26)%mod2+a[i]-'A')%mod2;
	}
	cod1=k1;
	cod2=k2;
}

int putere1(int a,int b)
{
	int k;
	if (b==1)
		return a;
	if (b%2==0)
	{
		k=putere1(a,b/2);
		return (k*k)%mod1;
	}
	return (a*putere1(a,b-1))%mod1;
}

int putere2(int a,int b)
{
	int k;
	if (b==1)
		return a;
	if (b%2==0)
	{
		k=putere2(a,b/2);
		return (k*k)%mod2;
	}
	return (a*putere2(a,b-1))%mod2;
}
void solve()
{
	int l;
	int c,cc1,cc2;
	l=a.size()-1;
	for (int i=0;i<=l;i++)
	{
		h1=((h1*26)%mod1+b[i]-'A')%mod1;
		h2=((h2*26)%mod2+b[i]-'A')%mod2;
	}
	c=0;
	if (h1==cod1 && h2==cod2)
	{
		nr++;
		poz.push_back(0);
	}
	for (int i=l+1;i<b.size();i++)
	{
		h1=h1-(putere1(26,l)*(b[c]-'A'))%mod1;
		h2=h2-(putere2(26,l)*(b[c]-'A'))%mod2;
		h1=((h1*26)%mod1+b[i]-'A')%mod1;
		h2=((h2*26)%mod2+b[i]-'A')%mod2;
		c++;
		if (h1==cod1 && h2==cod2)
		{
			nr++;
			poz.push_back(c);
		}
	}
}

void print()
{
	out<<nr<<"\n";
	for (int i=0;i<poz.size();i++)
		out<<poz[i]<<" ";
}

int main()
{
	scan();
	code(cod1,cod2);
	solve();
	print();
	return 0;
}