Cod sursa(job #3340005)

Utilizator Andrada_MincaAndrada Minca Andrada_Minca Data 11 februarie 2026 16:13:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
//
//  main.cpp
//  Potrivirea sirurilor cu hash
//
//  Created by Andrada Minca on 04.02.2026.
//

#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const int mod=1000000013;
long long putere(long long x, long long n)
{
    if(n==0)return 1;
    if(n==1)return x%mod;
    long long a=putere(x,n/2);
    a=a*a%mod;
    if(n%2==1)a*=x;
    a%=mod;
    return a;
}
int val(char x)
{
    return (int)x;
}
int main()
{
    string a,b;
    cin>>a>>b;
    //facem hash a
    long long hasha=0;
    for(int i=0;i<a.size();i++)
    {
        hasha=(hasha*130%mod+(int)a[i])%mod;
    }
    int n=a.size();
    long long hashb=0;
    for(int i=0;i<n;i++)
    {
        hashb=(hashb*130%mod+(int)b[i])%mod;
    }
    vector<int>ans;
    long long put=putere(130,n-1);
    put%=mod;
    if(hasha==hashb){ans.push_back(0);}
    for(int i=n;i<b.size();i++)
    {
        hashb=hashb-(int)b[i-n]*put;
        hashb%=mod;
        if(hashb<0)hashb+=mod;
        hashb=(hashb*130%mod+(int)b[i])%mod;
        if(hasha==hashb){ans.push_back(i-n+1);}
    }
    cout<<ans.size()<<'\n';
    int cv=ans.size();
    for(int i=0;i<min(1000,cv);i++)cout<<ans[i]<<" ";
    return 0;
}