Cod sursa(job #820197)

Utilizator mariacMaria Constantin mariac Data 20 noiembrie 2012 12:52:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<fstream>
#include<string.h>
#define mod 666013
#define mod2 100107
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[2000001], B[2000001];
int poz[1002];
int main()
{	int s1,s2,s21,s22,p21,p22,n=0,pf,pf2,i;
	fin.getline(A,2000001);
	fin.getline(B,2000001);
	s1=0;s2=0;
	i=1;
	pf=1;pf2=1;
	p21=1;p22=1;s21=0;s22=0;
	for(i=strlen(A)-1;i>=0;i--)
		{
			s1=(s1+(int)(A[i]-'0')*p21)%mod;
	    
			s2=(s2+(int)(A[i]-'0')*p22)%mod2;
			s21=(s21+(B[i]-'0')*p21)%mod;
	    
			s22=(s22+(B[i]-'0')*p22)%mod2;
		
			p21=(p21*75)%mod;
			p22=(p22*75)%mod2;
			if(i){
					pf=(pf*75)%mod;
					pf2=(pf2*75)%mod2;
				 }
		}
	if(strlen(A)<=strlen(B))
	{
		
	if(s21==s1&&s22==s2)
		{
			n++;
			poz[n]=0;
		}
	for(i=strlen(A);i<strlen(B);i++)
		{
			s21=((s21-(B[i-strlen(A)]-'0')*pf%mod+mod)%mod*75%mod+B[i]-'0')%mod;
			s22=((s22-(B[i-strlen(A)]-'0')*pf2%mod2+mod2)%mod2*75%mod2+B[i]-'0')%mod2;
			if(s21==s1&&s22==s2)if(n<1000)poz[++n]=i-strlen(A)+1;
									else n++;
		}
	}
	fout<<n<<"\n";
	for(i=1;i<=n&&i<=1000;i++)
		fout<<poz[i]<<" ";
	
	return 0;
}