Cod sursa(job #1279447)

Utilizator cdascaluDascalu Cristian cdascalu Data 30 noiembrie 2014 13:22:07
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include<iostream>
#include<fstream>
#include<string>
#include<vector>
#define B1 29
#define B2 101
#define MOD1 101119
#define MOD2 104033
using namespace std;

void read_data(string &A, string &B)
{
    ifstream f("strmatch.in");
    f>>A>>B;
    f.close();
}

void write_data(const int &nr_sol, const vector<int> &sol)
{
    ofstream g("strmatch.out");
    g<<nr_sol<<"\n";
    for(auto it = sol.begin();it != sol.end();++it)
        g<<*it<<" ";
    g.close();
}
int main()
{
    string A, B;
    read_data(A, B);

    int a_size = A.size(), b_size = B.size();

    int keyA1 = 0, keyA2 = 0, pow1 = 1, pow2 = 1, keyB1 = 0, keyB2 = 0;

    int nr_sol = 0;
    vector<int> sol;

    for(int i=0; i < a_size ; ++i)
    {
        keyA1 = ((keyA1 * B1) % MOD1 + A[i])%MOD1;
        keyA2 = ((keyA2 * B2) % MOD2 + A[i])%MOD2;

        if(i!=0)
        {
            pow1 *= B1;
            pow1 %= MOD1;
            pow2 *= B2;
            pow2 %= MOD2;
        }
    }

    for(int i=0;i < b_size;++i)
    {
        if(i < a_size)
        {
            keyB1 = ((keyB1 * B1)%MOD1 + B[i])%MOD1;
            keyB2 = ((keyB2 * B2)%MOD2 + B[i])%MOD2;
        }
        else {
            keyB1 = (((keyB1 - pow1 * B[i-a_size])%MOD1 + MOD1) * B1 + B[i])%MOD1;
            keyB2 = (((keyB2 - pow2 * B[i-a_size])%MOD2 + MOD2) * B2 + B[i])%MOD2;
        }

        if(keyB1 == keyA1 && keyB2 == keyA2)
        {
            if(nr_sol < 1000)
                sol.push_back(i - a_size + 1);
            ++nr_sol;
        }
    }

    write_data(nr_sol, sol);
    return 0;
}