Cod sursa(job #3250481)

Utilizator stefanvilcescuStefan Vilcescu stefanvilcescu Data 21 octombrie 2024 11:51:56
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <math.h>
#include <string>
#include <fstream>

const int MAXN=2e6;
const int MOD=980926811;
const int BASE=333352352;
const int MAXK=1000;

int hasha[MAXN+1];
int hashb[MAXN+1];
int put[MAXN+1];
int anspoz[MAXK];

void init_hashes(std::string s, std::string s1){
    int i, n, m;
    n=s.size();
    m=s1.size();
    put[0]=1;
    for(i=1; i<=MAXN; i++)
        put[i]=1LL*put[i-1]*BASE%MOD;
    for(i=1; i<=n; i++)
        hasha[i]=(1LL*hasha[i-1]*BASE+s[i-1])%MOD;
    for(i=1; i<=m; i++)
        hashb[i]=(1LL*hashb[i-1]*BASE+s1[i-1])%MOD;
}

int get_hash(int l, int r, int v[]){
    int ans=(v[r+1]-1LL*v[l]*put[r-l+1]%MOD+MOD)%MOD;
    return ans;
}

int main()
{
    std::ifstream cin("strmatch.in");
    std::ofstream cout("strmatch.out");
    int i, n, m, k;
    std::string s, s1;
    cin>>s>>s1;
    init_hashes(s, s1);
    n=s.size();
    m=s1.size();
    i=0;
    while(i<=m-n && k<MAXK){
        if(get_hash(0, n-1, hasha)==get_hash(i, i+n-1, hashb))
            anspoz[k++]=i;
        i++;
    }
    cout<<k<<"\n";
    for(i=0; i<k; i++)
        cout<<anspoz[i]<<" ";
    return 0;
}