Cod sursa(job #373788)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 15 decembrie 2009 01:39:40
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 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,Pow,E;
	int a,b,q;
	vector <int> S;
	strmatchRK(const int baza)
	{
		E=baza;
		a=b=0;
		q=100007;
	}
	void Read()
	{
		f>>A;
		f>>B;
		LenA=A.size();
		LenB=B.size();
		if(LenA>LenB)
		{
			g<<"0\n";
			exit(0);
		}
	}
	void Print()
	{
		g<<S.size()<<'\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;
	}
	bool cmp(int s)
	{
		for(int i=s,j=0;j<LenA;i++,j++)
			if(A[j]!=B[i])
				return 0;
		return 1;
	}
	void RK()
	{
		for(int i=0;i<LenA;i++)
		{
			a=(a*E+A[i])%q;
			b=(b*E+B[i])%q;
		}
		Pow=Putere(E,LenA-1,q);
		for(int i=0;i+LenA-1<=LenB;i++)
		{
			if((int)S.size()>=1000)
				return;
			if(a==b)
			{
				if(cmp(i))
					S.push_back(i);
			}
			if(i+LenA<=LenB)
				b=((b-(B[i]*Pow)%q+q)*E+B[i+LenA])%q;
		}
	}
};
int main()
{
	strmatchRK RK(73);
	RK.Read();
	RK.RK();
	RK.Print();
	return 0;
}