Cod sursa(job #373568)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 14 decembrie 2009 11:37:56
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include<fstream>
#include<string>
#include<vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
class strmatchRK
{
public:
	string A,B;
	int LenA,LenB,Pow,E;
	int a,b,q;
	vector <int> S;
	strmatchRK(const int baza)
	{
		E=baza;
		a=b=0;
		q=171110003;
	}
	void Read()
	{
		f>>A;
		f>>B;
		LenA=A.size();
		LenB=B.size();
	}
	void Print()
	{
		g<<S.size()<<'\n';
		for(int i=0;i<(int)S.size();i++)
			g<<S[i]<<' ';
		g<<'\n';
	}
	void PreCalc()
	{
		for(int i=0;i<LenA;i++)
		{
			a=(a*E+A[i])%q;
			b=(b*E+B[i])%q;
		}
	}
	int Putere(int a,int b)
	{
		int rez=1;
		a%=q;
		while(b)
		{
			if(b%2)
				rez=rez*a%q;
			a=a*a%q;
			b>>=1;
		}
		return rez;
	}
	bool cmp(int s)
	{
		for(int i=s,j=0;i<s+LenA;i++,j++)
			if(A[j]!=B[i])
				return 0;
		return 1;
	}
	void RK()
	{
		Pow=Putere(E,LenA-1);
		for(int i=0;i+LenA<=LenB+1;i++)
		{
			if(S.size()>1000)
				break;
			if(a==b)
			{
				if(cmp(i))
					S.push_back(i);
			}
			if(i<=LenB-LenA)
				b=(E*(b-B[i]*Pow)%q+B[i+LenA])%q;
		}
	}
};
int main()
{
	strmatchRK RK(123);
	RK.Read();
	RK.PreCalc();
	RK.RK();
	RK.Print();
	return 0;
}