Cod sursa(job #3236798)

Utilizator BogdanBurescuBogdan Burescu BogdanBurescu Data 1 iulie 2024 19:23:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <string>

using namespace std;

ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");

long long int t,n,i,j,m,x,y,s,sum,l,r,a[2000005],hash1,hash2[2000005],ans[1005],k,h,q,nr,p,maxi;
const int MOD=1e9+7;
string s1,s2;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>s1>>s2;
    n=s1.size();
    m=s2.size();
    a[0]=1;
    for(i=1; i<=2000000; i++)
        a[i]=(a[i-1]*127)%MOD;
    for(i=0; i<n; i++)
        hash1=(hash1*127+(s1[i]-'0'))%MOD;
    for(i=0; i<m; i++)
        hash2[i+1]=(hash2[i]*127+(s2[i]-'0'))%MOD;
    for(i=n; i<=m; i++)
    {
        q=(hash2[i]-(hash2[i-n]*a[n]%MOD)+MOD)%MOD;
        if(q==hash1)
        {
            nr++;
            if(nr<=1000)
            ans[nr]=i-n;
        }
    }
    cout<<nr<<'\n';
    nr=min(nr,1LL*1000);
    for(i=1; i<=nr; i++)
        cout<<ans[i]<<' ';
    return 0;
}