Cod sursa(job #2209772)

Utilizator verde.cristian2005Verde Flaviu-Cristian verde.cristian2005 Data 4 iunie 2018 17:50:37
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 2.36 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char smodel[2000001],s[2000001];
const int MOD1=666013,MOD2=673039,B=63;
int v[2000001];
int main()
{
    long long r1=0,r2=0,rmodel1=0,rmodel2=0,n1,n2,i,put1=1,put2=1,cnt=0;
    in>>(smodel+1);
    in>>(s+1);
    n1=strlen(smodel+1);
    n2=strlen(s+1);
    for(i=1; i<=n1; i++)
    {
        if(i>=2)
        {
            put1=put1*B%MOD1;
            put2=put2*B%MOD2;
        }
        rmodel1=(long long)rmodel1*B;
        if(smodel[i]>='A'&&smodel[i]<='Z')
            rmodel1+=smodel[i]-'A'+27;
        else if(smodel[i]>='a'&&smodel[i]<='z')
            rmodel1+=smodel[i]-'a'+1;
        else
            rmodel1+=smodel[i]-'0'+53;
        rmodel1%=MOD1;
        rmodel2=(long long)rmodel2*B;
        if(smodel[i]>='A'&&smodel[i]<='Z')
            rmodel2+=smodel[i]-'A'+27;
        else if(smodel[i]>='a'&&smodel[i]<='z')
            rmodel2+=smodel[i]-'a'+1;
        else
            rmodel2+=smodel[i]-'0'+53;
        rmodel2%=MOD2;
    }
    for(i=1; i<=n2; i++)
    {
        r1=(long long)r1*B;
        if(s[i]>='A'&&s[i]<='Z')
            r1+=s[i]-'A'+27;
        else if(s[i]>='a'&&s[i]<='z')
            r1+=s[i]-'a'+1;
        else
            r1+=s[i]-'0'+53;
        r1%=MOD1;
        r2=(long long)r2*B;
        if(s[i]>='A'&&s[i]<='Z')
            r2+=s[i]-'A'+27;
        else if(s[i]>='a'&&s[i]<='z')
            r2+=s[i]-'a'+1;
        else
            r2+=s[i]-'0'+53;
        r2%=MOD2;
        if(i>=n1)
        {
            if(rmodel1==r1&&rmodel2==r2)
            v[++cnt]=i-n1;
            if(s[i-n1+1]>='A'&&s[i-n1+1]<='Z')
                r1=r1+MOD1-put1*(s[i-n1+1]-'A'+27)%MOD1;
            else if(s[i-n1+1]>='a'&&s[i-n1+1]<='z')
                r1=r1+MOD1-put1*(s[i-n1+1]-'a'+1)%MOD1;
            else
                r1=r1+MOD1-put1*(s[i-n1+1]-'0'+53)%MOD1;
            r1%=MOD1;
            if(s[i-n1+1]>='A'&&s[i-n1+1]<='Z')
                r2=r2+MOD2-put2*(s[i-n1+1]-'A'+27)%MOD2;
            else if(s[i-n1+1]>='a'&&s[i-n1+1]<='z')
                r2=r2+MOD2-put2*(s[i-n1+1]-'a'+1)%MOD2;
            else
                r2=r2+MOD2-put2*(s[i-n1+1]-'0'+53)%MOD2;
            r2%=MOD2;
        }
    }
    out<<cnt<<'\n';
    for(i=1;i<=cnt;i++)
    out<<v[i]<<" ";
    return 0;
}