Cod sursa(job #715379)

Utilizator auRSTARHreapca Aurelian auRSTAR Data 17 martie 2012 09:01:32
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include<cstdio>
#include<cstring>
#include<vector>
#define MOD 666013
#define MOD1 100279
using namespace std;
vector<int> V;
void read(),solve();
int SAB1,SAB2,PRE1[200010],PRE2[200010],SOL1,SOL2,i,K,PRE3[200010],PRE4[200010],SAB3,SAB4,SOL3,SOL4;
char A[200010],B[200010],*p;
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf(" %s",A);
	scanf(" %s",B);
}
void solve()
{
	PRE1[0]=PRE2[0]=1;
	PRE3[0]=PRE4[0]=1;
	K=strlen(A);
	for(i=1;i<K;i++)
	{
		PRE1[i]=PRE1[i-1]*27;
		PRE1[i]%=MOD;
		PRE2[i]=PRE2[i-1]*29;
		PRE2[i]%=MOD;
		PRE3[i]=PRE3[i-1]*27;
		PRE3[i]%=MOD1;
		PRE4[i]=PRE4[i-1]*29;
		PRE4[i]%=MOD1;
	}
	for(p=A,--i;*p;p++,i--)
	{
		SAB1+=(*p-'0'+1)*PRE1[i];
		SAB1%=MOD;
		SAB2+=(*p-'0'+1)*PRE2[i];
		SAB2%=MOD;
		SAB3+=(*p-'0'+1)*PRE3[i];
		SAB3%=MOD1;
		SAB4+=(*p-'0'+1)*PRE4[i];
		SAB4%=MOD1;
	}
	for(p=B;*p;p++)
	{
		if(p-B<K)
		{
			SOL1+=(*p-'0'+1)*PRE1[K-(p-B)-1];
			SOL1%=MOD;
			SOL2+=(*p-'0'+1)*PRE2[K-(p-B)-1];
			SOL2%=MOD;
			SOL3+=(*p-'0'+1)*PRE3[K-(p-B)-1];
			SOL3%=MOD1;
			SOL4+=(*p-'0'+1)*PRE4[K-(p-B)-1];
			SOL4%=MOD1;
			continue;
		}
		if(SOL1==SAB1&&SOL2==SAB2&&SAB3==SOL3&&SAB4==SOL4)
		{
			V.push_back((p-B)-K);
			if(V.size()==1000)break;
		}
		SOL1-=(*(p-K)-'0'+1)*PRE1[K-1];
		while(SOL1<0)SOL1+=MOD;
		SOL2-=(*(p-K)-'0'+1)*PRE2[K-1];
		while(SOL2<0)SOL2+=MOD;
		SOL3-=(*(p-K)-'0'+1)*PRE3[K-1];
		while(SOL3<0)SOL3+=MOD1;
		SOL4-=(*(p-K)-'0'+1)*PRE4[K-1];
		while(SOL4<0)SOL4+=MOD1;
		SOL1*=27;SOL2*=29;
		SOL1%=MOD;SOL2%=MOD;
		SOL1+=(*p-'0'+1);
		SOL2+=(*p-'0'+1);
		SOL3*=27;SOL4*=29;
		SOL3%=MOD1;SOL4%=MOD1;
		SOL3+=(*p-'0'+1);
		SOL4+=(*p-'0'+1);
	}
	printf("%d\n",V.size());
	for(vector<int>::iterator it=V.begin();it!=V.end();it++)printf("%d ",*it);
}