Cod sursa(job #373872)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 15 decembrie 2009 12:40:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include<fstream>
#include<string>
#include<vector>
#include<stdlib.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define ll long long
class strmatchRK
{
public:
	string A,B;
	int LenA,LenB,N,Pow,E;
	int a[2],b[2],q[2],p[2];
	vector <int> S;
	strmatchRK(const int baza)
	{
		E=baza;
		a[0]=a[1]=b[0]=b[1]=0;
		q[0]=100007;q[1]=100021;
		N=0;
	}
	void Read()
	{
		f>>A;
		f>>B;
		LenA=A.size();
		LenB=B.size();
		if(LenA>LenB)
		{
			g<<"0\n";
			exit(0);
		}
	}
	void Print()
	{
		g<<N<<'\n';
		for(int i=0;i<(int)S.size();i++)
			g<<S[i]<<' ';
		g<<'\n';
	}
	int Putere(int a,int b,int q)
	{
		long rez=1;
		a=a%q;
		while(b)
		{
			if(b%2)
				rez=(ll)rez*a%q;
			a=(ll)a*a%q;
			b/=2;
		}
		return rez;
	}
	void RK()
	{
		for(int i=0;i<LenA;i++)
		{
			a[0]=(a[0]*E+A[i])%q[0];
			a[1]=(a[1]*E+A[i])%q[1];
			b[0]=(b[0]*E+B[i])%q[0];
			b[1]=(b[1]*E+B[i])%q[1];
		}
		p[0]=Putere(E,LenA-1,q[0]);
		p[1]=Putere(E,LenA-1,q[1]);
		for(int i=0;i+LenA-1<=LenB;i++)
		{
			if(a[0]==b[0]&&a[1]==b[1])
			{
				N++;
				if(N<=1000)
					S.push_back(i);
			}
			if(i+LenA<=LenB)
			{
				b[0]=((b[0]-(B[i]*p[0])%q[0]+q[0])*E+B[i+LenA])%q[0];
				b[1]=((b[1]-(B[i]*p[1])%q[1]+q[1])*E+B[i+LenA])%q[1];
			}
		}
	}
};
int main()
{
	strmatchRK RK(123);
	RK.Read();
	RK.RK();
	RK.Print();
	return 0;
}