Cod sursa(job #2284304)

Utilizator Mirela_MagdalenaCatrina Mirela Mirela_Magdalena Data 17 noiembrie 2018 10:26:02
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <cstring>

using namespace std;

char a[2000001], b[2000001];
int c[1002], o;

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

long long int p1, p2;

int h1(int n, int m, int l, char a[], long long int &p)
{
    int rez = 0;
    p = 1;
    for(int i=l-1; i>=0; i--)
    {
        rez = (rez + (a[i]-'A'+1)*p)%m;
        p*=n;
    }
    return rez;
}



int main()
{
    f>>a;
    f.get();
    f>>b;
    int l1 = strlen(a), l2 = strlen(b);
    int m = 199993;
    int ha = h1(2, m, l1, a, p1);
    int ha2 = h1(3, m, l1,a, p2);
    int hs1 = h1(2, m, l1, b, p1), hs2 = h1(3, m, l1, b, p2);
    p1/=2;
    p2/=3;
    if(ha == hs1 && ha2 == hs2)
    {
        c[o++] = 0;
    }
   for(int i=l1; i<l2; i++)
   {
        hs1 = (((hs1-(b[i-l1]-'A'+1)*p1 + m)*2)%m + (b[i]-'A'+1))%m;
        hs2 = (((hs2-(b[i-l1]-'A'+1)*p2 + m)*3)%m + (b[i]-'A'+1))%m;
        if(ha == hs1 && ha2 == hs2)
            c[o++] = i-l1+1;
    }
    g<<o<<"\n";
    for(int i=0; i<o; i++)
        g<<c[i]<<" ";

    return 0;
}