Cod sursa(job #2707891)

Utilizator Ionut_neuer58Raducu Ioan Stefan Ionut_neuer58 Data 17 februarie 2021 21:53:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
///#include <iostream>
#include <fstream>
#include <cstring>
#include <cmath>
const int SIZE = 2e6+100,
          MOD1 = 1e9+9,
          MOD2 = 666013,
          alpha = 62;

using namespace std;
typedef long long ll;

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

int charVal(char x)
{
    if('0'<=x && x<='9') return x-'0';
    if('a'<=x && x<='z') return x-'a'+10;
    if('A'<=x && x<='Z') return x-'A'+36;
    return -1;
}

int v[1010], vSize;

void RK(char s1[], char s2[])
{
    int n1=strlen(s1), n2=strlen(s2);
    if(n1>n2) return;
    ll hsh1=0, hsh2=0, val1=0, val2=0, p1=1, p2=1;
    for(int i=0; i<n1; i++)
    {
        if(i) p1=(p1*alpha)%MOD1, p2=(p2*alpha)%MOD2;
        hsh1=(hsh1*alpha+charVal(s2[i]))%MOD1;
        hsh2=(hsh2*alpha+charVal(s2[i]))%MOD2;
        val1=(val1*alpha+charVal(s1[i]))%MOD1;
        val2=(val2*alpha+charVal(s1[i]))%MOD2;
    }
    if(hsh1==val1 && hsh2==val2) v[vSize++]=0;
    for(int i=n1; i<n2; i++)
    {
        hsh1=(((hsh1-(charVal(s2[i-n1])*p1)%MOD1+MOD1)%MOD1)*alpha+charVal(s2[i]))%MOD1;
        hsh2=(((hsh2-(charVal(s2[i-n1])*p2)%MOD2+MOD2)%MOD2)*alpha+charVal(s2[i]))%MOD2;
        if(hsh1==val1 && hsh2==val2)
        {
            if(vSize<1000) v[vSize]=i-n1+1;
            vSize++;
        }
    }
}

char a[SIZE], b[SIZE];

int main()
{
    cin>>a>>b;
    RK(a, b);
    cout<<vSize<<'\n';
    for(int i=0; i<min(1000, vSize); i++)
        cout<<v[i]<<' ';
    return 0;
}