Cod sursa(job #490889)

Utilizator ChallengeMurtaza Alexandru Challenge Data 8 octombrie 2010 18:36:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <vector>
#include <string.h>

using namespace std;

const char InFile[]="strmatch.in";
const char OutFile[]="strmatch.out";
const int MaxN=2005000;
const int MOD=32103110;
const int BASE=62;

ifstream fin(InFile);
ofstream fout(OutFile);

char A[MaxN],B[MaxN];
int n,Ahash,Bhash;
vector<int> pos;

inline int val(char ch)
{
	if('0'<=ch && ch<='9')
	{
		return ch-'0';
	}
	if('a'<=ch && ch<='z')
	{
		return 11+ch-'a';
	}
	if('A'<=ch && ch<='Z')
	{
		return 38+ch-'A';
	}
	return BASE;
}

int main()
{
	fin>>A>>B;
	fin.close();

	int lenA=strlen(A);
	int lenB=strlen(B);
	if(lenA>lenB)
	{
		fout<<"0";
		fout.close();
		return 0;
	}
	for(register int i=0;i<lenA;++i)
	{
		Ahash*=BASE;
		Ahash+=val(A[i]);
		Ahash%=MOD;

		Bhash*=BASE;
		Bhash+=val(B[i]);
		Bhash%=MOD;
	}

	int BASEPA=1;
	for(register int i=1;i<lenA;++i)
	{
		BASEPA*=BASE;
		BASEPA%=MOD;
	}

	if(Ahash==Bhash)
	{
		if(pos.size()<1000)
		{
			pos.push_back(-1);
		}
		++n;
	}

	for(register int i=lenA;i<lenB;++i)
	{
		Bhash-=(BASEPA*val(B[i-lenA]))%MOD;
		if(Bhash<0)
		{
			Bhash+=MOD;
		}

		Bhash*=BASE;
		Bhash+=val(B[i]);
		Bhash%=MOD;

		if(Ahash==Bhash)
		{
			if(pos.size()<1000)
			{
				pos.push_back(i-lenA);
			}
			++n;
		}
	}


	fout<<n<<"\n";
	for(register int i=0;i<(int)pos.size();++i)
	{
		fout<<pos[i]+1<<" ";
	}
	fout.close();
	return 0;
}