Cod sursa(job #629542)

Utilizator selea_teodoraSelea Teodora selea_teodora Data 3 noiembrie 2011 14:37:22
Problema Potrivirea sirurilor Scor 24
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include<fstream>
#include<cstring>
using namespace std;
char a[2000005],b[2000005];
int n,m,baza=67,alfa1[2000005],alfa2[2000005],p=1000007;
int hash1,hash2;
int B[2000005];
int nra,poz[1005];
void putere()
{
	int i;
	B[0]=1;
	for(i=1;i<=m;i++)
		B[i]=(B[i-1]*baza)%p;
}
	
void transformare(char sir[],int lg1,int lg2,int alfab[],int &hash)
{
	int i;
	for(i=lg1;i<lg2;i++)
	{
		hash=(hash+(alfab[i]*B[lg2-i-1]))%p;
	}
}
int main()
{
	ifstream fin("strmatch.in");
	ofstream fout("strmatch.out");
	fin.getline(a,2000005);
	fin.getline(b,2000005);
	n=strlen(b);
	m=strlen(a);
	int i;
	for(i=0;i<m;i++)
		if(a[i]>='a'&&a[i]<='z')
		alfa2[i]=a[i]-'a';
		else
			if(a[i]>='A'&&a[i]<='Z')
				alfa2[i]=a[i]-'A'+25+1;
			else
				alfa2[i]=a[i]-'0'+25+25+2;
	for(i=0;i<n;i++)
		if(b[i]>='a'&&b[i]<='z')
			alfa1[i]=b[i]-'a';
		else
			if(b[i]>='A'&&b[i]<='Z')
				alfa1[i]=b[i]-'A'+25+1;
			else
				alfa1[i]=b[i]-'0'+25+25+2;
	putere();
	transformare(a,0,m,alfa2,hash2);
	transformare(b,0,m,alfa1,hash1);
	int sw=0;
	i=0;
	if(hash1==hash2)
	{
		for(i=0;i<m;i++)
			if(a[i]!=b[i])
				sw++;
		if(sw==0)
		{
			nra++;
			poz[0]++;
			poz[poz[0]]=1;
		}
	}
	i=1;
	while(i+m-1<=n)
	{
		hash1=(hash1-alfa1[i-1]*B[m-1])%p;
		if(hash1<0)
			hash1=hash1+p;
		hash1=(hash1*baza)%p;
		hash1=(hash1+alfa1[i+m-1])%p;
		sw=0;
		if(hash1==hash2)
		{
			for(int j=i;j<=m;j++)
				if(a[j]!=b[j])
					sw++;
			if(sw==0)
				{
				nra++;
				poz[0]++;
				poz[poz[0]]=i;
				}
		}
		i=i+1;
	}
	if(nra<=1000)
	{
		fout<<nra<<'\n';
		for(int j=1;j<=nra;j++)
			fout<<poz[j]<<" ";
		fout<<'\n';
	}
	return 0;
}