Cod sursa(job #1357416)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 23 februarie 2015 22:02:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <cstring>
#include <vector>
//#include <algorithm>

#define LMAX 2000005
#define mod 100007
#define base 127
using namespace std;

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

char a[LMAX], b[LMAX];
int n, m;
vector <int> sol;
long long a_hash, b_hash;

int main()
{
    fin >> a; n = strlen(a);
    fin >> b; m = strlen(b);
    long long x = 1;

    for (int i = 0; i < n; ++i)
    {
        a_hash = (a_hash * base + a[i]) % mod;

    }
    for (int i = 1; i < n; ++i) x = (x * base) % mod;

    for (int i = 0; i < n; ++i)
        b_hash = (b_hash * base + b[i]) % mod;
    if (b_hash == a_hash) sol.push_back(0);
    for (int i = n; i < m; ++i)
    {
        b_hash = ((b_hash - ((b[i-n] * x) % mod) + mod) * base + b[i]) % mod;

        if (a_hash == b_hash) sol.push_back(i-n+1);
    }

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