Cod sursa(job #2284346)

Utilizator Mirela_MagdalenaCatrina Mirela Mirela_Magdalena Data 17 noiembrie 2018 10:39:23
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 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 + 1LL*(a[i]-'A'+1)*p)%m;
        p = (p * n)%m;
    }
    return rez;
}



int main()
{
    f>>a;
    f.get();
    f>>b;
    int l1 = strlen(a), l2 = strlen(b);
    long long int m1 = 19999999993, m2 = 6660133793;
    long long int ha = h1(2, m1, l1, a, p1);
    long long int ha2 = h1(3, m2, l1,a, p2);
    long long int hs1 = h1(2, m1, l1, b, p1), hs2 = h1(3, m2, 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 + m1)*2)%m1 + (b[i]-'A'+1))%m1;
        hs2 = (((hs2-(b[i-l1]-'A'+1)*p2 + m2)*3)%m2 + (b[i]-'A'+1))%m2;
        if(ha == hs1 && ha2 == hs2)
        {
            if(o < 1000)
                c[o] = i-l1+1;
            o++;
        }
   }
    g<<o<<"\n";
    if(o > 999)
        for(int i=0; i<1000; i++)
            g<<c[i]<<" ";
    else for(int i=0; i<o; i++)
        g<<c[i]<<" ";

    return 0;
}