Cod sursa(job #3251013)

Utilizator proflaurianPanaete Adrian proflaurian Data 24 octombrie 2024 16:37:51
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string A,B;
int n,m,sol;
vector<int> poz;
int64_t p=666013,q=100003,ha,hb,ip,pn;
int64_t putere(int64_t b,int64_t e)
{
    if(e==0)
        return 1;
    int64_t r=putere(b,e/2);
    r=r*r%q;
    if(e%2==1)
        r=r*b%q;
    return r;
}
int main()
{
    f>>A>>B;
    n=A.size();
    for(int i=n-1;i>=0;i--) /// calculam valoarea hash pentru pattern-ul A
        ha=(ha*p+A[i])%q;
    for(int i=n-1;i>=0;i--) /// calculam valoarea hash pentru pattern-ul A
        hb=(hb*p+B[i])%q;
    ip=putere(p,q-2); /// ip = inversul modular al lui p modulo q
    pn=putere(p,n-1); /// pn = p^(n-1) modulo q
    if(ha==hb)
    {
        sol++;
        poz.push_back(0);
    }
    int st=0,dr=n-1;
    m=B.size();
    while(dr<m-1)
    {
        /// se scade din stanga
        hb=(hb-B[st]+q)%q;st++;
        /// se imparte prin p
        hb=hb*ip%q;
        /// se trece pe pozitia noua din dreapta la valoarea B[dr]
        dr++;
        /// se aduaga termenul B[dr] * p^n-1
        hb=(hb+pn*B[dr])%q;
        if(hb==ha)
        {
            sol++;
            if(sol<=1000)
                poz.push_back(st);
        }
    }
    g<<sol<<'\n';
    for(auto it:poz)
        g<<it<<' ';
    g<<'\n';
    return 0;
}