Cod sursa(job #3243048)

Utilizator davidgeo123Georgescu David davidgeo123 Data 15 septembrie 2024 13:32:31
Problema Potrivirea sirurilor Scor 94
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    string a, b;
    cin>>a>>b;
    int n=a.size(), m=b.size();
    a=" "+a;
    b=" "+b;

    const int MOD=1e9+9;
    const int base=53;
    vector<long long> pow(max(n, m)+1);
    pow[1]=1;
    for(int i=2; i<(int)pow.size(); i++)
        pow[i]=(pow[i-1]*base)%MOD;

    vector<long long> h(m+1, 0);
    for(int i=1; i<=m; i++)
        h[i]=(h[i-1]+(b[i]-'A'+1)*pow[i])%MOD;

    long long hash_a=0;
    for(int i=1; i<=n; i++)
        hash_a=(hash_a+(a[i]-'A'+1)*pow[i])%MOD;

    vector<int> pozitii;
    int cnt=0;

    for(int i=1; i+n-1<=m; i++)
    {
        long long cur_h = (h[i+n-1]+MOD-h[i-1])%MOD;
        if(cur_h == hash_a * pow[i] % MOD)
        {
            if(cnt<1000)
                pozitii.push_back(i-1);
            ++cnt;
        }
    }
    cout<<cnt<<'\n';
    for(auto x:pozitii)
        cout<<x<<' ';
    return 0;
}