Cod sursa(job #1228732)

Utilizator cdascaluDascalu Cristian cdascalu Data 15 septembrie 2014 11:13:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include<fstream>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<string>
#include<list>
#define Nmax 2000001
#define MOD1 82549
#define MOD2 99871
#define B1 29
#define B2 101
using namespace std;


void read(char *A, char *B)
{
    FILE*f = fopen("strmatch.in", "r");
    fscanf(f, "%s %s", A, B);
    fclose(f);
}
void write(const int &nr_sol, const list<int> &sol)
{
    FILE*g = fopen("strmatch.out", "w");
    fprintf(g, "%d\n", nr_sol);
    for(auto it = sol.begin(); it != sol.end(); ++it)
        fprintf(g, "%d ", *it);
    fclose(g);
}
int main()
{
    char A[Nmax], B[Nmax];
    read(A, B);

    int size_A = strlen(A);
    int size_B = strlen(B);

    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;
        }
    }

    int nr_sol = 0;
    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)
        {
            if(nr_sol < 1000)
                sol.push_back(i - size_A + 1);
            ++nr_sol;
        }
    }

    write(nr_sol, sol);
    return 0;
}