Cod sursa(job #3251028)

Utilizator proflaurianPanaete Adrian proflaurian Data 24 octombrie 2024 16:49:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.68 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 q=666013,p=100003,ha,hb,ip,pn;
int64_t Q=100003,P=666013,HA,HB,IP,PN;
int64_t putere(int64_t b,int64_t e,int q)
{
    if(e==0)
        return 1;
    int64_t r=putere(b,e/2,q);
    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;
        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;
        HB=(HB*P+B[i])%Q;
    }
    ip=putere(p,q-2,q); /// ip = inversul modular al lui p modulo q
    pn=putere(p,n-1,q); /// pn = p^(n-1) modulo q
    IP=putere(P,Q-2,Q); /// ip = inversul modular al lui p modulo q
    PN=putere(P,n-1,Q); /// pn = p^(n-1) modulo q
    if(ha==hb && 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;
        HB=(HB-B[st]+Q)%Q;st++;
        /// se imparte prin p
        hb=hb*ip%q;
        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;
        HB=(HB+PN*B[dr])%Q;
        if(hb==ha && HB==HA)
        {
            sol++;
            if(sol<=1000)
                poz.push_back(st);
        }
    }
    g<<sol<<'\n';
    for(auto it:poz)
        g<<it<<' ';
    g<<'\n';
    return 0;
}