Cod sursa(job #2593557)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 4 aprilie 2020 10:35:48
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2 kb
#include <bits/stdc++.h>

using namespace std;
/*****************************************/
const int m1=100007;
const int m2=100021;
const int p=101;

string A;
string B;

int nA;
int nB;

int hash1,hash2,h1,h2;

int rasp;

int p1=1,p2=1;

bool nuVerifica=false;

int v[2000001];

/*****************************************/
ifstream f("strmatch.in");
ofstream g("strmatch.out");
/*****************************************/
///--------------------------------------------------
inline void readInput()
{
    f>>A>>B;
    nA=A.length();
    nB=B.length();
}
///--------------------------------------------------
inline void creeareHashA()
{
    for(int i=0;i<nA;i++)
    {
        hash1=hash1*p%m1 + A[i];
        hash2=hash2*p%m2 + A[i];
        if(i!=0)
        {
            p1=p1*p%m1;
            p2=p2*p%m2;
        }
    }
    if(nA>nB) nuVerifica=true;
}
///--------------------------------------------------
inline void creeareHashB()
{
    for(int i=0;i<nA;i++)
    {
        h1=h1*p%m1+B[i];
        h2=h2*p%m2+B[i];
    }
    if(hash1==h1 && hash2==h2)
    {
        rasp++;
        v[0]=1;
    }
}
///--------------------------------------------------
inline void Comparare()
{
    for(int i=nA;i<nB;i++)
    {
        h1=((h1-B[i-nA]*p1%m1+m1)*p+B[i])%m1;
        h2=((h2-B[i-nA]*p2%m2+m2)*p+B[i])%m2;

        if(hash1==h1 && hash2==h2)
        {
            v[i-nA+1]=1;
            rasp++;
        }
    }
}
///--------------------------------------------------
inline void Afisare()
{
    g<<rasp<<"\n";

    for(int i=0;i<nB;i++)
    {
        if(v[i]==1) g<<i<<" ";
    }
}
///--------------------------------------------------
inline void Solution()
{
    creeareHashA();
    if(nuVerifica==true)
    {
        g<<"0"<<"\n";
        return;
    }
    creeareHashB();
    Comparare();
    Afisare();
}
///--------------------------------------------------
int main()
{
    readInput();
    Solution();
    return 0;
}