Cod sursa(job #1228728)

Utilizator cdascaluDascalu Cristian cdascalu Data 15 septembrie 2014 10:59:34
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include<fstream>
#include<iostream>
#include<string>
#include<list>
#define MOD1 99991
#define MOD2 99871
#define B1 10
#define B2 23
using namespace std;


void read(string &A, string &B)
{
    ifstream f("strmatch.in");
    f>>A>>B;
    f.close();
}
void write(const list<int> &sol)
{
    ofstream g("strmatch.out");
    g<<sol.size()<<"\n";
    for(auto it = sol.begin(); it != sol.end(); ++it)
        g<<*it<<" ";
    g.close();
}
int main()
{
    string A, B;
    read(A, B);

    int size_A = A.length();
    int size_B = B.length();
    int keyA1 = 0, keyA2 = 0, keyB1 = 0, keyB2 = 0, PB1 = 1, PB2 = 1;

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

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

    for(int i=0; i < size_B; ++i)
    {
        if(i >= size_A)
        {
            keyB1 = (((keyB1 - PB1 * B[i-size_A]) % MOD1 + MOD1) * B1 + B[i]) % MOD1;
            keyB2 = (((keyB2 - PB2 * B[i-size_A]) % MOD2 + MOD2) * B2 + B[i]) % MOD2;
        }
        else
        {
            keyB1 = ((keyB1 * B1) + B[i])%MOD1;
            keyB2 = ((keyB2 * B2) + B[i])%MOD2;
        }

        if(keyB1 == keyA1 && keyB2 == keyA2)
            sol.push_back(i - size_A + 1);
    }

    write(sol);
    return 0;
}