Cod sursa(job #2974205)

Utilizator LuxinMatMatasaru Luxin Gabriel LuxinMat Data 3 februarie 2023 15:43:23
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 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 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 ah = 0;
    pow[0] = 1;
    for(int i=0; i<n; i++)
    {
        add(ah, a[i], MOD1);
        add(hesh1, b[i], MOD1);
        if(i)
            pow[i] = (pow[i-1] * BASE) % int(1e9 + 7);
    }

    int rez = 0;
    if(hesh1 == ah)
    {
        rez++;
        r.push_back(0);
    }

    for(int i=n; i<m && rez <= 1000; i++)
    {
        hesh1 -= (b[i-n]*pow[n-1])%MOD1;
        add(hesh1, b[i], MOD1);

        if(hesh1 == ah)
        {
            rez++;
            r.push_back(i-n+1);
        }
    }

    cout<<rez<<'\n';
    for(int nr : r)
        cout<<nr<<" ";
    return 0;
}