Cod sursa(job #2871562)

Utilizator Danut200333Dumitru Daniel Danut200333 Data 15 martie 2022 08:42:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define MOD1 1000000007
#define MOD2 1000000013
#define hash1 33
#define hash2 37
string A,B;
long long n,m,hashA1,hashA2,p1,p2,hashB1,hashB2,x;
vector <int> sol;
int main()
{
    fin>>A>>B;
    n=B.size();
    m=A.size();
    p1=p2=1;
    for(int i=0;i<m;i++)
    {
        hashA1=((hashA1*hash1)%MOD1+A[i])%MOD1;
        hashA2=((hashA2*hash2)%MOD2+A[i])%MOD2;
        if(i>0)
        {
            p1=(p1*hash1)%MOD1;
            p2=(p2*hash2)%MOD2;
        }
    }
    for(int i=0;i<m;i++)
    {
        hashB1=((hashB1*hash1)%MOD1+B[i])%MOD1;
        hashB2=((hashB2*hash2)%MOD2+B[i])%MOD2;
    }
    if(hashA1==hashB1&&hashA2==hashB2)
    {
        sol.push_back(0);
    }
    for(int i=m;i<n;i++)
    {
        hashB1=((hash1*(hashB1-((B[i-m]*p1)%MOD1)+MOD1))%MOD1+B[i])%MOD1;
        hashB2=((hash2*(hashB2-((B[i-m]*p2)%MOD2)+MOD2))%MOD2+B[i])%MOD2;
        if(hashB1==hashA1&&hashB2==hashA2)
        {
            sol.push_back(i-m+1);
        }
    }
    fout<<sol.size()<<'\n';
    for(int i=0;i<sol.size()&&i<1000;i++)fout<<sol[i]<<" ";
    return 0;
}