Cod sursa(job #2236961)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 31 august 2018 04:32:20
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.87 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream fin("strmatch.in");

class OutParser {
private:
    FILE *fout;
    char *buff;
    int sp;

    void write_ch(char ch) {
        if (sp == 50000) {
            fwrite(buff, 1, 50000, fout);
            sp = 0;
            buff[sp++] = ch;
        } else {
            buff[sp++] = ch;
        }
    }


public:
    OutParser(const char* name) {
        fout = fopen(name, "w");
        buff = new char[50000]();
        sp = 0;
    }
    ~OutParser() {
        fwrite(buff, 1, sp, fout);
        fclose(fout);
    }

    OutParser& operator << (int vu32) {
        if (vu32 <= 9) {
            write_ch(vu32 + '0');
        } else {
            (*this) << (vu32 / 10);
            write_ch(vu32 % 10 + '0');
        }
        return *this;
    }

    OutParser& operator << (long long vu64) {
        if (vu64 <= 9) {
            write_ch(vu64 + '0');
        } else {
            (*this) << (vu64 / 10);
            write_ch(vu64 % 10 + '0');
        }
        return *this;
    }

    OutParser& operator << (char ch) {
        write_ch(ch);
        return *this;
    }
    OutParser& operator << (const char *ch) {
        while (*ch) {
            write_ch(*ch);
            ++ch;
        }
        return *this;
    }
};

OutParser fout("strmatch.out");

typedef long long ll;

const ll MOD=1000000007;
const int N=2000000;
const int BASE=62;

ll expow(ll a,ll b)
{
    ll ans=1;
    while(b>0)
    {
        if(b%2==1)
            ans=(ll)ans*a%MOD;
        a=(ll)a*a%MOD;
        b/=2;
    }
    return ans;
}

char s[N+5];
int len1;
int len2;

ll inv,add;

ll f(char ch)
{
    if('0'<=ch && ch<='9')
        return ch-'0';
    if('a'<=ch && ch<='z')
        return ch-'a'+10;
    return ch-'A'+36;
}

ll caut=0;

int cnt=0;
int sol[1005];

int main()
{
    fin.getline(s,N+5);
    len1=strlen(s);
    inv=expow(62,MOD-2);
    add=expow(62,len1-1);
    ll cur=1;
    for(int i=0;i<len1;i++)
    {
        caut=(caut+(ll)cur*f(s[i]))%MOD;
        cur=(ll)cur*62%MOD;
    }
    fin.getline(s,N+5);
    len2=strlen(s);
    if(len2<len1)
    {
        fout<<"0\n";
        return 0;
    }
    ll am=0;
    cur=1;
    for(int i=0;i<len1;i++)
    {
        am=(am+(ll)cur*f(s[i]))%MOD;
        cur=(ll)cur*62%MOD;
    }
    if(am==caut)
    {
        sol[++cnt]=0;
    }
    for(int st=1;st+len1-1<len2;st++)
    {
        am-=f(s[st-1]);
        if(am<0)
            am+=MOD;
        am=(ll)am*inv%MOD;
        am=(am+(ll)add*f(s[st+len1-1]))%MOD;
        if(am==caut)
        {
            if(cnt<1000)
                sol[++cnt]=st;
            else
                cnt++;
        }
    }
    fout<<cnt<<"\n";
    for(int i=1;i<=min(cnt,1000);i++)
        fout<<sol[i]<<" ";
    fout<<"\n";
    return 0;
}