Cod sursa(job #2974218)

Utilizator Andrei_Gagea08Andrei Gagea Andrei_Gagea08 Data 3 februarie 2023 15:56:35
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.92 kb
#include <fstream>
#include <cstring>
#define MOD1 100021 ///1000000009
#define MOD2 100007 ///1000000007

using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

char v[2000001];
int s[1001];

int main()
{
    bool pp=true;
    int n=1,m;
    long long nr1=0,nr2=0,ns1=0,ns2=0;
    long long p1=1,p2=1;
    int sol=0;
    char ch;


    ///0-9 => 0-9
    ///a-z => 10-35
    ///A-Z => 36-61

    cin.get(ch);
    if('0'<=ch && ch<='9')
    {
        nr1+=ch-'0';
        nr2+=ch-'0';
    }
    else if('a'<=ch && ch<='z')
    {
        nr1+=ch-'a'+10;
        nr2+=ch-'a'+10;
    }
    else if('A'<=ch && ch<='Z')
    {
        nr1+=ch-'A'+36;
        nr2+=ch-'A'+36;
    }
    while(pp==true)
    {
        cin.get(ch);
        if(ch=='\n')
            pp=false;
        else
        {
            n++;
            p1*=62;
            p2*=62;
            p1=p1%MOD1;
            p2=p2%MOD2;
            if('0'<=ch && ch<='9')
            {
                nr1+=p1*(ch-'0');
                nr1%=MOD1;
                nr2+=p2*(ch-'0');
                nr2%=MOD2;
            }
            else if('a'<=ch && ch<='z')
            {
                nr1+=p1*(ch-'a'+10);
                nr1%=MOD1;
                nr2+=p2*(ch-'a'+10);
                nr2%=MOD2;
            }
            else if('A'<=ch && ch<='Z')
            {
                nr1+=p1*(ch-'A'+36);
                nr1%=MOD1;
                nr2+=p2*(ch-'A'+36);
                nr2%=MOD2;
            }
        }
    }
    cin.getline(v,2000001);
    m=strlen(v);
    if(n>m)
        cout<<0;
    else
    {
        int i=1;
        ch=v[n];
        p1=1;
        p2=1;
        if('0'<=ch && ch<='9')
        {
            ns1+=ch-'0';
            ns2+=ch-'0';
        }
        else if('a'<=ch && ch<='z')
        {
            ns1+=ch-'a'+10;
            ns2+=ch-'a'+10;
        }
        else if('A'<=ch && ch<='Z')
        {
            ns1+=ch-'A'+36;
            ns2+=ch-'A'+36;
        }
        for(i=n-1;i>=1;i--)
        {
            ch=v[i];
            p1*=62;
            p2*=62;
            p1=p1%MOD1;
            p2=p2%MOD2;
            if('0'<=ch && ch<='9')
            {
                ns1+=p1*(ch-'0');
                ns1%=MOD1;
                ns2+=p2*(ch-'0');
                ns2%=MOD2;
            }
            else if('a'<=ch && ch<='z')
            {
                ns1+=p1*(ch-'a'+10);
                ns1%=MOD1;
                ns2+=p2*(ch-'a'+10);
                ns2%=MOD2;
            }
            else if('A'<=ch && ch<='Z')
            {
                ns1+=p1*(ch-'A'+36);
                ns1%=MOD1;
                ns2+=p2*(ch-'A'+36);
                ns2%=MOD2;
            }
        }
        for(i=n+1;i<=m;i++)
        {
            if(nr1==ns1 && nr2==ns2)
            {
                sol++;
                if(sol<=1000)
                    s[sol]=i-n;
            }
            ch=v[i-n];
            if('0'<=ch && ch<='9')
                ch=ch-'0';
            else if('a'<=ch && ch<='z')
                    ch=ch-'a'+10;
            else if('A'<=ch && ch<='Z')
                    ch=ch-'A'+36;
            ns1=ns1-1LL*(p1*ch)%MOD1+MOD1;
            ns2=ns2-1LL*(p2*ch)%MOD2+MOD2;
            ns1*=62;
            ns2*=62;
            ch=v[i];
            if('0'<=ch && ch<='9')
                ch=ch-'0';
            else if('a'<=ch && ch<='z')
                    ch=ch-'a'+10;
            else if('A'<=ch && ch<='Z')
                    ch=ch-'A'+36;
            ns1+=ch;
            ns2+=ch;
            ns1%=MOD1;
            ns2%=MOD2;
        }
        if(nr1==ns1 && nr2==ns2)
        {
            sol++;
            if(sol<=1000)
                s[sol]=i-n;
        }
        cout<<sol<<'\n';
        for(i=1;i<=sol && i<=1000;i++)
            cout<<s[i]<<" ";
    }
    return 0;
}