Cod sursa(job #3195015)

Utilizator BreabanDanielBreaban Daniel-Vasile BreabanDaniel Data 19 ianuarie 2024 22:03:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
#include <fstream>
#include <cstring>
#include <vector>
#define MOD 100007
#define MOD1 100021
#define BASE 73
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
long long int y,z,hashA,hashA1,hashB,hashB1,p=1,p1=1,contor;
vector <int> A;
vector <int> B;
vector <int> ans;

char s[20000007];
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;
    }
    for(int i=0;i<aux;i++)
    {
        hashA=(hashA*BASE+A[i])%MOD;
        hashA1=(hashA1*BASE+A[i])%MOD1;
        hashB1=(hashB1*BASE+B[i])%MOD1;
        hashB=(hashB*BASE+B[i])%MOD;
        if(i!=0)
        {
            p=p*BASE%MOD;
            p1=p1*BASE%MOD1;
        }
    }
    if(hashA==hashB && hashA1==hashB1)
    {
        contor++;
        ans.push_back(0);
    }
    for(int i=aux;i<B.size();i++)
    {
        hashB=((hashB-B[i-aux]*p%MOD+MOD)*BASE+B[i])%MOD;
        hashB1=((hashB1-B[i-aux]*p1%MOD1+MOD1)*BASE+B[i])%MOD1;
        if(hashB==hashA && hashB1==hashA1)
        {
            contor++;
            if(contor<=1000)
            {
                ans.push_back(i-aux+1);
            }
        }
    }
    fout<<contor<<'\n';
    for(int i=0;i<ans.size();i++)
        fout<<ans[i]<<' ';
    return 0;
}