Cod sursa(job #2284395)

Utilizator Mirela_MagdalenaCatrina Mirela Mirela_Magdalena Data 17 noiembrie 2018 10:50:48
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 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]*p)%m)%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 = 40099, m2 = 319993;
    long long int ha = h1(31, m1, l1, a, p1);
    long long int ha2 = h1(53, m2, l1,a, p2);
    long long int hs1 = h1(31, m1, l1, b, p1), hs2 = h1(53, m2, l1, b, p2);
    p1/=31;
    p2/=53;
    if(ha == hs1 && ha2 == hs2)
    {
        c[o++] = 0;
    }
   for(int i=l1; i<l2; i++)
   {
        hs1 = (((hs1-((b[i-l1])*p1)%m1 + m1)*31)%m1 + b[i])%m1;
        hs2 = (((hs2-((b[i-l1])*p2)%m2 + m2)*53)%m2 + b[i])%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;
}