Cod sursa(job #1991579)

Utilizator Alexandru05Giurgea Alexandru Alexandru05 Data 17 iunie 2017 14:25:54
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int chtoiaA0(char ch)
{
    if(('0'<=ch)&&(ch<='9'))
    {
        return ch-'0'+1;
    }
    if(('a'<=ch)&&(ch<='z'))
    {
        return ch-'a'+11;
    }
    else
        return ch-'A'+37;
}

int main()
{
    string a,b;
    vector<int> x;
    int R1=0,R2=0,B=63;
    int pow1=1,pow2=1;
    int mod1=666013,mod2=666019;
    fin>>a;
    fin>>b;
    int asize=a.size(),bsize=b.size();
    int mare1=1LL*mod1*(B+1), mare2=mod2*(B+1);
    for(int i=0;i<asize;i++)
    {
        R1=(R1*1LL*B+(chtoiaA0(a[i])))%mod1;
        R2=(R2*1LL*B+(chtoiaA0(a[i])))%mod2;
    }
    int r1=0,r2=0, ans=0;
    for(int i=0;i<bsize;i++)
    {
        if(i<asize-1)
        {
            pow1=(pow1*B)%mod1;
            pow2=(1LL*pow2*B)%mod2;
        }
        if(i>=asize)
        {
            r1=(r1-pow1*(chtoiaA0(b[i-asize]))+mare1)%mod1;
            r2=(r2-pow2*(chtoiaA0(b[i-asize]))+mare2)%mod2;
        }
        r1=(r1*B+(chtoiaA0(b[i])))%mod1;
        r2=(r2*B+(chtoiaA0(b[i])))%mod2;
        if(i>=asize-1)
        {
            if(R1==r1 && R2==r2)
            {
                ans++;
                if(x.size()<1000)
                    x.push_back(i-asize);
            }
        }
    }
    fout<<ans<<'\n';
    for(int i:x)
    {
        fout<<i+1<<" ";
    }
    return 0;
}