Cod sursa(job #1798420)

Utilizator cicero23catalin viorel cicero23 Data 5 noiembrie 2016 10:57:54
Problema Potrivirea sirurilor Scor 26
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");

ofstream g("strmatch.out");
int b1,b2,x,x2,y,y2,v[1001],k,kmax,z;
char s[2000001],p[2000001];
int has1(int N, int i)
{
    N=((N+701-(s[i-1]*b1)%701)*128+s[i+strlen(p)-1])%701;
    return N;
}
int has2(int N, int i)
{
    N=((N+797-(s[i-1]*b2)%797)*128+s[i+strlen(p)-1])%797;
    return N;

}
int main()
{
    int i,j;
   f>>p;
   f.get();
    f>>s;

    b1=1;
    b2=1;
    for(i=1;i<strlen(p);i++)
    {
        b1=(b1*128)%701;
        b2=(b2*128)%797;
    }

    for(i=0;i<strlen(p);i++)
    {
     x=((x*128)%701+p[i])%701;
     x2=((x2*128)%797+p[i])%797;
      y=((y*128)%701+s[i])%701;
       y2=((y2*128)%797+s[i])%797;
    }
    if(x==y&&x2==y2)
    {
        v[0]=1;
        kmax=1;
        v[++z]=0;
    }
   for(i=1;i<=strlen(s)-strlen(p)+1;i++)
    {

        y=has1(y,i);
        y2=has2(y2,i);
        if(x==y&&x2==y2){if(z<=1000)v[++z]=i; kmax++;}
    }

   /*while(i<strlen(p))
    {
        k=1;
        while(v[i]==0) i++;
        for(j=i;j<=strlen(s)-strlen(p);j+=4)
        {
            while(v[j]==0)j++;
            k++;
        }
        if(k>kmax)kmax=k;
        i++;
    }*/
    g<<kmax<<'\n';
    for(i=1;i<=z;i++)
        g<<v[i]<<" ";
    return 0;
}