Cod sursa(job #1254659)

Utilizator dica69Alexandru Lincan dica69 Data 3 noiembrie 2014 09:23:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <cstdio>
#include <cstring>


using namespace std;

FILE *f1,*f2;
long Q1=666013;
long Q2=100021;
long b=73;
char A[2000001],B[2000001];
long n,m,i,p[123],sol[2000001],k,x1,x2,t1,t2,p1,p2;
int main()
{f1 = fopen("strmatch.in","r");
f2 = fopen("strmatch.out","w");
fgets(A,2000001,f1);
fgets(B,2000001,f1);
n=strlen(B)-1;m=strlen(A)-1;
if (m>n) {fprintf(f2,"0\n");fclose(f2);return 0;}

x1=x2=1;
for (i=1;i<m;i++)
{x1=(x1*b)%Q1;
x2=(x2*b)%Q2;
}
t1=t2=p1=p2=0;
for (i=0;i<m;i++)
{p1=(p1*b+(long)A[i])%Q1;
p2=(p2*b+(long)A[i])%Q2;
t1=(t1*b+(long)B[i])%Q1;
t2=(t2*b+(long)B[i])%Q2;
}
if (t1==p1 && t2==p2) sol[++k]=0;

for (i=m;i<n;i++)
{
t1=((t1-(B[i-m]*x1)%Q1+Q1)*b+B[i])%Q1;
t2=((t2-(B[i-m]*x2)%Q2+Q2)*b+B[i])%Q2;
if (t1==p1 && t2==p2) sol[++k]=i-m+1;
}


fprintf(f2,"%ld\n",k);
for (i=1;i<=k;i++) fprintf(f2,"%ld ",sol[i]);
fclose(f1);fclose(f2);
    return 0;
}

//Challenges are what make life interesting and overcoming them is what makes life meaningful.