Cod sursa(job #1427921)

Utilizator daniel.grosuDaniel Grosu daniel.grosu Data 3 mai 2015 12:41:06
Problema Potrivirea sirurilor Scor 66
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include<fstream>
#include<string>
#include<sstream>
#define MOD 3
using namespace std;

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

int i,j,s;
stringstream result;
string a,b;
long long ha, hb;

long long pow(int n, int p)
{
	unsigned long long a=n;
	unsigned long long sol=1;
	for(int i=0; (1<<i) <= p; ++i)
	{
		if(((1<<i)&p) > 0)
			sol=sol*a;
		a=a*a;
	}
	return sol;
}

int main()
{
	fin>>a;
	fin>>b;
	for(i=0; i<a.length(); ++i)
		ha+=pow(MOD,a.length()-i-1)*a[i];
		
	for(i=0; i<a.length(); ++i)
		hb+=pow(MOD,a.length()-i-1)*b[i];

	for(i=0; i<b.length()-a.length()+1; ++i)
	{
		if(ha==hb)
		{
			bool q=true;
			for(j=0; j<a.length(); ++j)
				if(a[j] != b[i+j]) q=false;
			if(q){
				if(s<1000)
					result<<i<<" ";
				s++;
			}
		}
		hb=MOD*(hb-pow(MOD, a.length()-1)*b[i]) + b[i+a.length()];
	}
	fout<<s<<endl;
	fout<<result.str();
	return 0;
}