Cod sursa(job #3282598)

Utilizator BogdanBurescuBogdan Burescu BogdanBurescu Data 6 martie 2025 10:01:03
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <vector>
#include <queue>
#include <string>

using namespace std;

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

const int MOD=1e9+7;
long long int n,m,u,v,a[2000005],hash2[2000005],grad[50005],ans[2005],nr,hash1;
vector<int>g[50005];
queue<int>q;
string s1,s2;

int main()
{
    cin>>s1;
    cin>>s2;
    n=s1.size();
    m=s2.size();

    a[0]=1;
    for(int i=1;i<=2000005;i++)
        a[i]=a[i-1]*127%MOD;
    for(int i=0;i<n;i++)
        hash1=(hash1*127+(s1[i]-'0'))%MOD;
    for(int i=0;i<m;i++)
        hash2[i+1]=(hash2[i]*127+(s2[i]-'0'))%MOD;

    for(int i=n;i<=m;i++)
    {
        int k=(hash2[i]-(hash2[i-n]*a[n])%MOD+MOD)%MOD;
        if(hash1==k)
        {
            nr++;
            if(nr<=1000)
                ans[nr]=i-n;
        }
    }
    cout<<nr<<'\n';
    nr=min(nr,1LL*1000);
    for(int i=1; i<=nr; i++)
        cout<<ans[i]<<' ';
    return 0;
}