Cod sursa(job #3194081)

Utilizator BreabanDanielBreaban Daniel-Vasile BreabanDaniel Data 16 ianuarie 2024 21:33:46
Problema Potrivirea sirurilor Scor 2
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <vector>
#define MOD 10000007
#define MOD2 20000007
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
long long int y,z,valA,valA2,valB,valB2,contor;
long long int baza26[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++)
        A.push_back(s[j]-'A');
    fin>>s;
    for(int j=0;s[j];j++)
        B.push_back(s[j]-'A');
    int aux=A.size();
    baza26[0]=1;
    for(int i=1;i<=aux;i++)
        baza26[i]=26*baza26[i-1]%MOD;
    valA=updateA(0,aux-1);

    for(int i=0;i<B.size()-aux+1;i++)
    {
        valB=updateB(i,i+aux-1);
        if(valB==valA)
        {
            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;
    for(int i=st;i<=dr;i++)
    {
        x+=A[i]*baza26[dr-st]%MOD;
    }
    return x;
}

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