Cod sursa(job #812699)

Utilizator mariacMaria Constantin mariac Data 14 noiembrie 2012 11:33:13
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include<fstream>
#include<string.h>
#include<ctype.h>
#define mod 666013
#define mod2 1000122
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,p1,p2,p21,p22,n=0,pf,pf2,i;
	fin.getline(A,2000001);
	fin.getline(B,2000001);
	strlwr(A);
	strlwr(B);
	p1=1;p2=1;s1=0;s2=0;
	i=1;
	pf=1;pf2=1;
	while(i<strlen(A)){pf=(pf*26)%mod;pf2=(pf2*26)%mod2;i++;}
	for(i=strlen(A)-1;i>=0;i--)
		{
			s1=(s1+(int)(A[i]-'a')*p1)%mod;
	    
			s2=(s2+(int)(A[i]-'a')*p2)%mod2;
		
			p1=(p1*26)%mod;
			p2=(p2*26)%mod2;
		}
	if(strlen(A)<=strlen(B))
	{
		p21=1;p22=1;s21=0;s22=0;
		for(i=strlen(A)-1;i>=0;i--)
			{
				s21=(s21+(B[i]-'a')*p21)%mod;
	    
				s22=(s22+(B[i]-'a')*p22)%mod2;
		
				p21=(p21*26)%mod;
				p22=(p22*26)%mod2;
			}
	}
	if(s21==s1&&s22==s2){n++; poz[n]=0;}
	for(i=strlen(A);i<strlen(B);i++)
		{
			s21=((s21-(B[i-strlen(A)]-'a')*pf)*26%mod+B[i]-'a')%mod;
			s22=((s22-(B[i-strlen(A)]-'a')*pf2)*26%mod2+B[i]-'a')%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;
}