Cod sursa(job #3030342)

Utilizator DomnulMilandruMilandru Nicon-David DomnulMilandru Data 17 martie 2023 17:03:28
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb

#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char A[2000001],B[2000001];
int NA,NB;
const int M1=100021;
const int M2=100007;
long long hash1,hash2,hash1B,hash2B;
long long P1,P2;
long long nr;
vector<int> pozitii;
int main()
{
    cin>>A>>B;
    NA=strlen(A);
    NB=strlen(B);
    if(NA>NB)
    {
        cout<<0;
        return 0;
    }
    P1=1;
    P2=1;
    for(int i=0;i<NA;i++)
    {
        hash1=(hash1*256+A[i])%M1;
        hash2=(hash2*256+A[i])%M2;
        hash1B=(hash1B*256+B[i])%M1;
        hash2B=(hash2B*256+B[i])%M2;
        if(i)
        {
            P1=(P1*256)%M1;
            P2=(P2*256)%M2;
        }
    }
    if(hash1==hash1B && hash2==hash2B)
    {
       nr++;
       pozitii.push_back(0);
    }
    for(int i=1;i<=NB-NA;i++)
    {
        hash1B=(((hash1B-B[i-1]*P1)%M1+M1)*256+B[i+NA-1])%M1;
        hash2B=(((hash2B-B[i-1]*P2)%M2+M2)*256+B[i+NA-1])%M2;
        if(hash1==hash1B && hash2==hash2B)
        {
        nr++;
        pozitii.push_back(i);
        }
    }
    cout<<nr<<'\n';
    for(int i=0;i<pozitii.size();i++)
      cout<<pozitii[i]<<" ";
    return 0;
}