Cod sursa(job #3003546)

Utilizator DomnulMilandruMilandru Nicon-David DomnulMilandru Data 15 martie 2023 19:47:10
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char A[2000001],B[2000001];
int hash1A,hash2A,hash1,hash2;
int P1,P2,M1,M2,nr;
vector<int> pozitii;
int main()
{
    cin>>A;
    cin>>B;
    int NA=strlen(A);
    int NB=strlen(B);
    P1=1;
    P2=1;
    const int M1=100007;
    const int M2=100021;
    if(NA>NB)
       {
           cout<<0;
           return 0;
       }
    for(int i=0;i<NA;i++)
    {
        hash1A=(hash1A*216+A[i])%M1;
        hash2A=(hash2A*216+A[i])%M2;
        hash1=(hash1*216+B[i])%M1;
        hash2=(hash2*216+B[i])%M2;
        if(i!=0)
        {
        P1=(P1*216)%M1;
        P2=(P2*216)%M2;
        }
    }
    if(hash1==hash1A && hash2==hash2A)
    {
        nr++;
        pozitii.push_back(0);
    }
    for(int i=1;i<=NB-NA;i++)
     {
        hash1=(((hash1-(B[i-1]*P1))%M1+M1)*216+B[i+NA-1])%M1;
        hash2=(((hash2-(B[i-1]*P2))%M2+M2)*216+B[i+NA-1])%M2;
         if(hash1A==hash1 && hash2A==hash2)
         {
              nr++;
        pozitii.push_back(i);
         }
     }
    cout<<nr<<'\n';
    if(nr>1000)
           for(int i=0;i<1000;i++)
             cout<<pozitii[i]<<" ";
       else
           for(int i=0;i<nr;i++)
             cout<<pozitii[i]<<" ";
    return 0;
}