Cod sursa(job #2909914)

Utilizator aminaAmina Suciu amina Data 16 iunie 2022 20:09:33
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include<vector>

using namespace std;
const int mod=666013;


int hashfunction(string s)
{
    int value=0, pow256=1;
    for(int i=0; i<s.size(); i++)
    {


      value=(value+ pow256*s[s.size()-i-1])%mod;
      pow256=(256*pow256)%mod;

    }
    return value;
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    string B="AnacalAna";
    string A="Ana";
    cin>>A>>B;
    int hashvalA=hashfunction(A);

int hashval=hashfunction(B.substr(0,A.size()));


 int p256=1;
 for(int i=1; i<A.size(); i++)
 {
     p256=(256*p256)%mod;
 }
 vector <int> raspuns;
 raspuns.resize(0);
 if(hashval==hashvalA)raspuns.push_back(0);

 for(int i=A.size(); i<B.size(); i++)
 {
     hashval=hashval-(p256*B[i-A.size()])%mod;
     if (hashval<0) hashval+=mod;

     hashval=(hashval*256+B[i])%mod;
     if(hashval==hashvalA)raspuns.push_back(i-A.size()+1);

 }

 cout<<raspuns.size()<<endl;
 for(int i=0; i<raspuns.size();i++)
    cout<<raspuns[i]<<' ';





}