Cod sursa(job #2483845)

Utilizator XXMihaiXX969Gherghinescu Mihai Andrei XXMihaiXX969 Data 30 octombrie 2019 13:52:30
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.94 kb
#include <iostream>
#include <fstream>
#include <string.h>
#include <algorithm>

using namespace std;


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

const int DIM =  2000005;

const long long cst1 = 100021;
const long long cst2 = 100007;
const int nr = 50;

char a[DIM];
char b[DIM];

long long power1[DIM];
long long power2[DIM];
int rez[DIM];

int main()
{
    /*functia hash se face cu puterile nr de litere posibile din vector in cazul acesta sunt nr de litere mici si mari din alfabet englez adica 52 */
    in >> a;
    in >> b;

    int  K = 0;
    power1[0] = 1;
    power2[0] = 1;
    int A = strlen(a);
    for(int i = 1;i <= A;i++)
    {
     power1[i] = (power1[i - 1] * nr )% cst1;
     power2[i] = (power2[i - 1] * nr )% cst2;
    }
    int B = strlen(b);
    if(A > B)
    {out << 0;
    return 0;
    }

    long long S1 = 0;
    long long S2 = 0;
    long long val1 = 0;
    long long val2 = 0;
    for(int i = 0;i < A;i++)
    {
        val1 += (power1[A - i - 1] * (int(a[i]) - 46)) % cst1;
        val1 %= cst1;
        val2 += (power2[A - i - 1] * (int(a[i]) - 46)) % cst2;
        val2 %= cst2;
        S1 += (power1[A - i - 1] *(int (b[i]) - 46)) % cst1;
        S1 %= cst1;
        S2 += (power2[A - i - 1] *(int (b[i]) - 46)) % cst2;
        S2 %= cst2;
    }
    if(S1 == val1 && S2 == val2)
    {K++;
    rez[K] = 0;
    }
    for(int i = 1; i <= B - A;i++)
    {
        S1 = (((S1 - power1[A - 1] * (int(b[i-1]) - 46)) % cst1 * nr )% cst1 + (int(b[i + A - 1]) - 46)) % cst1;
        S2 = (((S2 - power2[A - 1] * (int(b[i-1]) - 46)) % cst2 * nr )% cst2 + (int(b[i + A - 1]) - 46)) % cst2;
        if(S1 == val1 && S2 == val2)
        {
            K++;
            rez[K] = i;
        }
    }
    out << K<<"\n";
    /* normal K ,in cazul asta e restrictie de 1000 de afisari*/
    for(int i = 1; i <= min(1000,K); i++)
        out << rez[i] <<" ";
    return 0;
}