Cod sursa(job #3296280)

Utilizator iordacheMatei Iordache iordache Data 12 mai 2025 11:42:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
const int N=2e6+5;int p=251,mod=1e9+7;
int put[N],invput[N];
int pref[N];
int binpow(int n, int e)
{
    int ans=1;
    while(e)
    {
        if(e&1) ans=ans*n%mod;
        n=n*n%mod;
        e>>=1;
    }
    return ans;
}
int inv(int x) {return binpow(x,mod-2);}
signed main()
{
    ifstream cin("strmatch.in");ofstream cout("strmatch.out");
    string s,t;
    cin>>t>>s;
    int n=s.size(),m=t.size();
    s='?'+s;t='?'+t;
    put[0]=1;invput[0]=inv(1);
    int invp=inv(p);
    for(int i=1;i<=n;++i) {put[i]=put[i-1]*p%mod;invput[i]=invput[i-1]*invp%mod;}
    for(int i=1;i<=n;++i) pref[i]=(pref[i-1]+s[i]*put[i-1]%mod)%mod;
    int hsh=0;
    for(int j=1;j<=m;++j)
    {
        hsh=(hsh+t[j]*put[j-1]%mod)%mod;
    }
    vector<int> sol;
    for(int i=1;i+m-1<=n;++i)
    {
        int x=(pref[i+m-1]-pref[i-1]+mod)%mod;
        x=x*invput[i-1]%mod;
        if(x==hsh) sol.pb(i);
    }
    cout<<min((long long)sol.size(),1000ll)<<'\n';
    for(auto x:sol) cout<<x-1<<" ";
}