Cod sursa(job #3194084)

Utilizator BreabanDanielBreaban Daniel-Vasile BreabanDaniel Data 16 ianuarie 2024 21:47:32
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.02 kb
#include <fstream>
#include <cstring>
#include <vector>
#define MOD 1000000007
#define MOD1 20000007
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
long long int y,z,valA,valA1,valB,valB1,contor;
int baza61M[2000007];
int baza61M1[2000007];
vector <int> A;
vector <int> B;
vector <int> ans;

char s[20000007];
long long int updateA(int st,int dr);
long long int updateB(int st,int dr);
int main()
{
    fin>>s;
    for(int j=0;s[j];j++)
    {
        if(isdigit(s[j]))
            A.push_back(s[j]-'0');
        else
        if(islower(s[j]))
            A.push_back(s[j]-'a'+10);
        else
            A.push_back(s[j]-'a'+36);
    }
    fin>>s;
    for(int j=0;s[j];j++)
    {
        if(isdigit(s[j]))
            B.push_back(s[j]-'0');
        else
        if(islower(s[j]))
            B.push_back(s[j]-'a'+10);
        else
            B.push_back(s[j]-'a'+36);
    }
    int aux=A.size();
    if(aux>B.size())
    {
        fout<<0;
        return 0;
    }
    baza61M[0]=1;
    baza61M1[0]=1;
    for(int i=1;i<=aux;i++)
    {
        baza61M[i]=61*baza61M[i-1]%MOD;
        baza61M1[i]=61*baza61M1[i-1]%MOD1;

    }
    valA=updateA(0,aux-1);

    for(int i=0;i<B.size()-aux+1;i++)
    {
        valB=updateB(i,i+aux-1);
        if(valB==valA && valB1==valA1)
        {
            contor++;
            if(contor<=1000)
            {
                ans.push_back(i);
            }
        }
    }
    fout<<contor<<'\n';
    for(int i=0;i<ans.size();i++)
        fout<<ans[i]<<' ';
    return 0;
}

long long int updateA(int st,int dr)
{
    long long int x=0;
    valA1=0;
    for(int i=st;i<=dr;i++)
    {
        x+=A[i]*baza61M[dr-st]%MOD;
        valA1+=A[i]*baza61M1[dr-st]%MOD1;
    }
    return x;
}

long long int updateB(int st,int dr)
{
    long long int x=0;
    valB1=0;
    for(int i=st;i<=dr;i++)
    {
        x+=B[i]*baza61M[dr-st]%MOD;
        valB1+=B[i]*baza61M1[dr-st]%MOD1;
    }
    return x;
}