Cod sursa(job #2209776)

Utilizator verde.cristian2005Verde Flaviu-Cristian verde.cristian2005 Data 4 iunie 2018 18:09:49
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 4.08 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[1001];
int main()
{
    long long r1=0,r2=0,rmodel1=0,rmodel2=0;
    int n1,n2,i,put1=1,put2=1,cnt=0;
    in>>(smodel+1);
    in>>(s+1);
    n1=strlen(smodel+1);
    n2=strlen(s+1);
    if(n1>n2)
        out<<0;
    else
    {
        for(i=1; i<=n1; i++)
        {
            if(i>=2)
            {
                put1=put1*B%MOD1;
                put2=put2*B%MOD2;
            }
            rmodel1=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=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<=n1-1; i++)
        {
            r1=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=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)
                    cnt++;
                if(rmodel1==r1&&rmodel2==r2&&cnt<=1000)
                    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;
            }
        }
        for(; i<=n2; i++)
        {
            r1=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=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(rmodel1==r1&&rmodel2==r2)
                cnt++;
            if(rmodel1==r1&&rmodel2==r2&&cnt<=1000)
                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<<n1<<" "<<n2<<" ";
        out<<cnt<<'\n';
        cnt=min(cnt,1000);
        for(i=1; i<=cnt; i++)
            out<<v[i]<<" ";
    }
    return 0;
}