Cod sursa(job #2974215)

Utilizator LuxinMatMatasaru Luxin Gabriel LuxinMat Data 3 februarie 2023 15:51:07
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 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];
int pow[LMAX];

vector<int> r;

void add(int& hesh, int nr, int mod)
{
    hesh = ((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;
    pow[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)
            pow[i] = (pow[i-1] * BASE) % int(1e9 + 7);
    }

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

    for(int i=n; i<m; i++)
    {
        hesh1 -= (b[i-n]*pow[n-1])%MOD1;
        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;
}