Cod sursa(job #2976776)

Utilizator LuxinMatMatasaru Luxin Gabriel LuxinMat Data 9 februarie 2023 23:18:39
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include<fstream>
#include<cstring>
#include<vector>
using namespace std;

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

const int BASE = 128;
const int MOD1 = 1e9 + 7;
const int MOD2 = 1;
const int LMAX = 2000001;

char a[LMAX], b[LMAX];
uint64_t pow1[LMAX], pow2[LMAX];

vector<int> r;

void add(int& hesh, int nr, int mod)
{
    hesh = ((1LL * hesh * BASE)%mod + nr)%mod;
}

int main()
{
    cin>>a>>b;
    int n = strlen(a);
    int m = strlen(b);

    int hesh1 = 0;
    int hesh2 = 0;
    int ah1 = 0;
    int ah2 = 0;
    pow1[0] = 1;
    pow2[0] = 1;
    for(int i=0; i<n; i++)
    {
        add(ah1, a[i], MOD1);
        add(ah2, a[i], MOD2);
        add(hesh1, b[i], MOD1);
        add(hesh2, b[i], MOD2);
        if(i)
        {
            pow1[i] = (pow1[i-1] * BASE) % MOD1;
            pow2[i] = (pow2[i-1] * BASE) % MOD2;
        }
    }

    int rez = 0;
    if(hesh1 == ah1 && ah2 == hesh2)
    {
        rez++;
        r.push_back(0);
    }

    for(int i=n; i<m; i++)
    {
        hesh1 -= (b[i-n]*pow1[n-1])%MOD1;
        hesh2 -= (b[i-n]*pow2[n-1])%MOD2;
        add(hesh1, b[i], MOD1);
        add(hesh2, b[i], MOD2);

        if(hesh1 == ah1 && ah2 == hesh2)
        {
            rez++;
            r.push_back(i-n+1);
        }
    }

    cout<<rez<<'\n';
    for(int i=0; i<r.size() && i<1000; i++)
        cout<<r[i]<<" ";
    return 0;
}