Cod sursa(job #3296755)

Utilizator InformaticianInDevenire1Munteanu Mihnea Gabriel InformaticianInDevenire1 Data 16 mai 2025 15:52:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

int MOD = 1e9+7;
int baza = 1024;
int pws[2000005],hsh[2000005];

void Build_Rolly_Hashy_Hash(string S){
    int n = S.size();
    for (int i=n-1;i>=0;--i) hsh[i] = ((1LL*hsh[i+1]*baza)%MOD+S[i])%MOD;
    return;
}

void Build_Powery_Powers(string S){
    int n = S.size();
    pws[0] = 1;
    for (int i=1;i<=n;++i) pws[i] = (1LL*pws[i-1]*baza)%MOD;
    return;
}

int Build_Hashy_Hash(string S){
    int n = S.size(),h = 0;
    for (int i=n-1;i>=0;--i) h = ((1LL*h*baza)%MOD+S[i])%MOD;
    return h;
}

int GetSeq(int L,int R){
    return ((hsh[L]-(1LL*hsh[R+1]*pws[R-L+1])%MOD)%MOD+MOD)%MOD;
}

int main()
{
    string a,b;
    fin >> a;
    fin >> b;
    Build_Rolly_Hashy_Hash(b);
    Build_Powery_Powers(b);
    int h = Build_Hashy_Hash(a),ans = 0;
    for (int i=0;i+a.size()-1<b.size();i++){
        if (GetSeq(i,i+a.size()-1)==h) ans++;
    }
    fout << ans << '\n';
    int cnt = 0;
    for (int i=0;i+a.size()-1<b.size();i++){
        if (cnt<1000 and GetSeq(i,i+a.size()-1)==h){
            fout << i << ' ';
            cnt++;
        }
    }
    return 0;
}