Cod sursa(job #1357787)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 24 februarie 2015 08:53:54
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <iostream>
#include <cstring>
#include <vector>
//#include <algorithm>

#define LMAX 2000005
#define mod1 100007
#define mod2 100021

#define base1 127
#define base2 126
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

//char a[LMAX], b[LMAX];
string a, b;
int n, m;
vector <int> sol;
long long a_hash1, b_hash1;
long long a_hash2, b_hash2;

int main()
{
    fin >> a; n = (a.size());
    fin >> b; m = (b.size());
    long long x1 = 1, x2 = 1;
    sol.reserve(1005);

    for (int i = 0; i < n; ++i)
    {
        a_hash1 = (a_hash1 * base1 + a[i]) % mod1;
        a_hash2 = (a_hash2 * base2 + a[i]) % mod2;

    }
    for (int i = 1; i < n; ++i)
    {
        x1 = (x1 * base1) % mod1;
        x2 = (x2 * base2) % mod2;
    }
    for (int i = 0; i < n; ++i)
    {
        b_hash1 = (b_hash1 * base1 + b[i]) % mod1;
        b_hash2 = (b_hash2 * base2 + b[i]) % mod2;
    }
    if (b_hash1 == a_hash1 && b_hash2 == a_hash2) sol.push_back(0);
    for (int i = n; i < m; ++i)
    {
        b_hash1 = ((b_hash1 - ((b[i-n] * x1) % mod1) + mod1) * base1 + b[i]) % mod1;
        b_hash2 = ((b_hash2 - ((b[i-n] * x2) % mod2) + mod2) * base2 + b[i]) % mod2;
        if (a_hash1 == b_hash1 && a_hash2 == b_hash2) sol.push_back(i-n+1);
    }

    int dim = min((int)sol.size(), 1000);
    fout << sol.size() << '\n';
    for (int i = 0; i < dim; ++i)
        fout << sol[i] << ' ';
    fout << '\n';
    return 0;
}