Cod sursa(job #2207369)

Utilizator AndreiCroitoruAndrei Croitoru AndreiCroitoru Data 25 mai 2018 16:03:03
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <fstream>
#include <cstring>
#define p1 90917
#define p2 666013
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
inline int scif(char ch)
{
    if(ch>='0' && ch<='9')
        return ch - '0';
    if(ch >= 'A' and ch <= 'Z')
        return ch - 'A' + 10;
    return ch - 'a' + 36;
}
char ch1[2000000],ch2[2000000];
int v[1001];
int main()
{
    long long nr=0,p=1;
    int l,i,r1,r2,rr1,rr2;
    int k;
    in.get(ch1,2000000);
    in.get();
    in.get(ch2,2000000);
    k=strlen(ch1);
    l=strlen(ch2);
    for(i=0;i<k;i++)
    {
        nr+=p*(scif(ch1[i]));
        p*=62;
        p%=p1;
    }
    r1=nr%p1;
    p=1;
    nr=0;
    int q=0;
    for(i=0;i<k;i++)
    {
        nr+=p*(scif(ch1[i]));
        p*=62;
        p%=p2;
    }
    r2=nr%p2;
    long long n,z;
    p=1;
    for(i=0;i<k;i++)
    {
        n+=p*(scif(ch2[i]));
        z=p;
        p*=62;
        p%=p1;
    }
    rr1=n%p1;
    n=0;
    p=1;
    long long z2,cn;
    for(i=0;i<k;i++)
    {
        n+=p*(scif(ch2[i]));
        z2=p;
        p*=62;
        p%=p2;
    }
    rr2=n%p2;
    cn=n;
    if(r1==rr1 && r2==rr2)
       {
           q++;
           v[q]=i;
       }
    for(i=1;i<l-k;i++)
    {
       n+=p1;
       n-=((scif(ch2[i-1])*z)%p1);
       n=(62*n)%p1;
       n=(n+scif(ch2[i+k]))%p1;

       rr1=n%p1;
       cn+=p2;
       cn-=((scif(ch2[i-1])*z)%p2);
       cn=(62*cn)%p2;
       cn=(n+scif(ch2[i+k]))%p2;
       rr2=cn%p2;
       if(r1==rr1 && r2==rr2)
       {
           q++;
           v[q]=i;
       }
    }
    out<<q<<'\n';
    if(q>1000)
        q=1000;
    for(i=1;i<=q;i++)
        out<<v[i]<<" ";
    return 0;
}