Cod sursa(job #1519747)

Utilizator valentinpielePiele Valentin valentinpiele Data 7 noiembrie 2015 19:36:06
Problema Potrivirea sirurilor Scor 28
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include <fstream>
#include <cstring>
#define MOD1 100007
#define MOD2 666013
#define P 73
using namespace std;

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

const int Lmax = 2000010;

char str1[Lmax], str2[Lmax];
int potrivire[Lmax];

int N, M;

int str1b1, str1b2;
int str2b1, str2b2;
int putere1, putere2;

int nrmatchuri;

int main ()
{
    f.get(str1, sizeof(str1));
    f.get();
    f.get(str2, sizeof(str2));

    M = strlen(str1);
    N = strlen(str2);

    if(M > N) { g << '0' << '\n'; return 0;}

    str1b1 = str1b2 = 0;
    putere1 = putere2 = 1;

    for(int i = 0; i < M; i ++)
    {
        str1b1 = (str1b1 * P + str1[i]) % MOD1;
        str1b2 = (str1b2 * P + str1[i]) % MOD2;

        if(i != 1)
        {
            putere1 = (putere1 * P) % MOD1;
            putere2 = (putere2 * P) % MOD2;
        }
    }

    str2b1 = str2b2 = 0;
    nrmatchuri = 0;

    for(int i = 0; i < M; i ++)
    {
        str2b1 = (str2b1 * P + str2[i]) % MOD1;
        str2b2 = (str2b2 * P + str2[i]) % MOD2;
    }

    if(str1b1 == str2b1 && str1b2 == str2b2)
    {
        nrmatchuri += 1;
        potrivire[0] = 1;
    }

    for(int i = M; i < N; i ++)
    {
        str2b1 = ((str2b1 - (str2[i - M] * putere1) % MOD1 + MOD1) * P + str2[i]) % MOD1;
        str2b2 = ((str2b2 - (str2[i - M] * putere2) % MOD2 + MOD2) * P + str2[i]) % MOD2;

        if(str1b1 == str2b1 && str1b2 == str2b2)
        {
            nrmatchuri += 1;
            potrivire[i - M + 1] = 1;
        }
    }

    g << nrmatchuri << '\n';
    nrmatchuri = 0;
    for(int i = 0; i < N && nrmatchuri < 1000; i ++) { if(potrivire[i]) g << i << ' '; nrmatchuri ++; }

    g << '\n';
    return 0;
}