Cod sursa(job #3337686)

Utilizator jarnea_justinjarnea justin ioan jarnea_justin Data 29 ianuarie 2026 15:28:39
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <bits/stdc++.h>
using namespace std;
#define mod1 1000000007
#define mod2 1000000009
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string a,b;
int ha2[2000001],hb2[2000001],pw2[2000001],ha1[2000001],hb1[2000001],pw1[2000001];
int val(char c)
{
    if('a'<=c && c<='z')
        return c-'a'+1;
    else if('0'<=c && c<='9')
        return c-'0'+53;
    else return c-'A'+27;
}
pair<int,int> hash_substr(int l,int r)
{
    int h1=(hb1[r]-1LL*hb1[l-1]*pw1[r-l+1]%mod1+mod1)%mod1;
    int h2=(hb2[r]-1LL*hb2[l-1]*pw2[r-l+1]%mod2+mod2)%mod2;
    return {h1,h2};
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    f>>a>>b;
    a=' '+a;
    b=' '+b;
    int base1=37;
    int base2=39;
    for(int i=1; i<a.size(); i++)
    {
        ha1[i]=(1LL*base1*ha1[i-1]+val(a[i]))%mod1;
        ha2[i]=(1LL*base2*ha2[i-1]+val(a[i]))%mod2;
    }
    for(int i=1; i<b.size(); i++)
    {
        hb1[i]=(1LL*base1*hb1[i-1]+val(b[i]))%mod1;
        hb2[i]=(1LL*base2*hb2[i-1]+val(b[i]))%mod2;
    }
    pw1[0]=1;
    pw2[0]=1;
    for(int i=1; i<=b.size(); i++)
    {
        pw1[i]=(1LL*pw1[i-1]*base1)%mod1;
        pw2[i]=(1LL*pw2[i-1]*base2)%mod2;
    }
    vector<int> sol;
    int n=b.size()-1,m=a.size()-1;
    pair<int,int> hash_a={ha1[a.size()-1],ha2[a.size()-1]};

    for(int i=1; i+m-1<b.size(); i++)
        if(hash_substr(i,i+m-1)==hash_a)
            if(sol.size()<1000)
                sol.push_back(i-1);
            else break;
    g<<sol.size()<<'\n';
    for(auto x:sol)
        g<<x<<" ";
    return 0;
}