Cod sursa(job #1423359)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 21 aprilie 2015 19:08:38
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include<fstream>
#include<string>
#include<vector>
#include<cstring>
#define NMAX 2000010
#define base 67
#define MOD1 104729
#define MOD2 666013
#define egale hA1==hB1 && hA2==hB2

using namespace std;

char A[NMAX], B[NMAX];
vector<int> sol;
long long hA1, hA2, hB1, hB2, base_pow1, base_pow2, potriviri_suplimentare=0;

inline long long valoare(char c)
{
    if (c>='A' && c<='Z') return c-'A';
    if (c>='a' && c<='z') return 'z'-'a'+c-'a';
    return ('z'-'a')*2+c-'0';
}

long long compute(string S, int st, int dr, long long MOD)
{
    long long rez=0;
    for (int i=st; i<dr; ++i)
    {
        rez=(rez*base+valoare(S[i]))%MOD;
    }
    return rez;
}

void putere(int N)
{
    base_pow1=base_pow2=1;

    for (int i=1; i<=N; ++i)
    {
        base_pow1=(base_pow1*base)%MOD1;
        base_pow2=(base_pow2*base)%MOD2;
    }
}


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

    f>>A>>B;
    int lgA=strlen(A), lgB=strlen(B);

    putere(lgA-1);

    hA1=compute(A, 0, lgA, MOD1);
    hA2=compute(A, 0, lgA, MOD2);
    hB1=compute(B, 0, lgA, MOD1);
    hB2=compute(B, 0, lgA, MOD2);

    if (egale)
    {
        sol.push_back(0);
    }

    for (int i=lgA; i<lgB; ++i)
    {
        hB1=hB1-(base_pow1*valoare(B[i-lgA]))%MOD1;
        if (hB1<0) hB1+=MOD1;
        hB1=(hB1*base+valoare(B[i]))%MOD1;

        hB2=hB2-(base_pow2*valoare(B[i-lgA]))%MOD2;
        if (hB2<0) hB2+=MOD2;
        hB2=(hB2*base+valoare(B[i]))%MOD2;

        if (egale)
        {
            if (sol.size()<1000) sol.push_back(i-lgA+1);
            else ++potriviri_suplimentare;
        }
    }

    g<<sol.size()+potriviri_suplimentare<<"\n";
    for (int i=0; i<sol.size(); ++i)
        g<<sol[i]<<" ";
    g<<"\n";

    return 0;
}