Cod sursa(job #2209778)

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