Cod sursa(job #2707859)

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

using namespace std;
typedef long long ll;

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

char a[SIZE], b[SIZE];
int v[1010], vSize;

int chVal(char ch)
{
    if('a'<=ch && ch<='z') return ch-'a';
    else if('A'<=ch && ch<='Z') return ch-'A'+26;
    else if('0'<=ch && ch<='9') return ch-'0'+52;
    return -1;
}

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, pam1=1, pam2=1;
    for(int i=0; i<n1; i++)
    {
        hsh1=(hsh1*alpha+chVal(s2[i]))%MOD1;
        hsh2=(hsh2*alpha+chVal(s2[i]))%MOD2;
        val1=(val1*alpha+chVal(s1[i]))%MOD1;
        val2=(val2*alpha+chVal(s1[i]))%MOD2;
        if(i)
            pam1=(pam1*alpha)%MOD1,
            pam2=(pam2*alpha)%MOD2;
    }
    if(hsh1==val1 && hsh2==val2) v[vSize++]=0;
    for(int i=n1; i<n2; i++)
    {
        hsh1=((hsh1-(chVal(s2[i-n1])*pam1)%MOD1+MOD1)*alpha+chVal(s2[i]))%MOD1;
        hsh2=((hsh2-(chVal(s2[i-n1])*pam2)%MOD2+MOD2)*alpha+chVal(s2[i]))%MOD2;
        if(hsh1==val1 && hsh2==val2)
        {
            if(vSize<1000) v[vSize]=i-n1+1;
            vSize++;
        }
    }
}

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;
}