Cod sursa(job #3137383)

Utilizator proflaurianPanaete Adrian proflaurian Data 12 iunie 2023 19:04:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int P=666013;
const int Q=1000000007;
inline int prod(int X,int Y){X=1LL*X*Y%Q;return X;}
inline int suma(int X,int Y){X=(X+Y)%Q;return X;}
inline int diff(int X,int Y){X=(X-Y+Q)%Q;return X;}
string a,b;
int cnt;
vector<int> sol;
int main()
{
    f>>a>>b;
    int n=a.size(),m=b.size();
    /// calculez valoarea hash pentru a
    int p=1;
    int valA=a[0];
    for(int i=1;i<n;i++)
    {
        p=prod(p,P);/// aici calulez p=P^(n-1)
        valA=suma(prod(valA,P),int(a[i]));/// aici calculez valoarea asociata lui a
    }
    int valB=b[0];
    for(int i=1;i<n-1;i++)
        valB=suma(prod(valB,P),b[i]);
    for(int st=0,dr=n-1;dr<m;st++,dr++)
    {
        valB=suma(prod(valB,P),int(b[dr]));
        if(valA==valB)
        {
            cnt++;
            if(cnt<=1000)
                sol.push_back(st);
        }
        valB=diff(valB,prod(p,int(b[st])));
    }
    g<<cnt<<'\n';
    for(auto it:sol)
        g<<it<<' ';
    return 0;
}