Cod sursa(job #2284498)

Utilizator Mihnea_11Mihnea Lopataru Mihnea_11 Data 17 noiembrie 2018 11:17:32
Problema Potrivirea sirurilor Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

#define NMAX 2000005

char p[NMAX], t[NMAX], n, m;
long long nr, v[1000], k = 0;

struct Hash
{
    long long n, m, power, hash;

    void init (char *s, int  len)
    {
        power = 1, hash = 0;
        for(int i = len - 1; i >= 0; --i)
        {
            hash = (hash + 1LL * power * s[i]) % m;
            if(i)
                power = (power * n) % m;
        }
    }

    void roll (char toRemove, char toADD)
    {
        hash = (((hash - toRemove * power + m) * n) % m + toADD) % m;
    }
};


int main()
{

    f >> p >> t;
    n = strlen(p);
    m = strlen(t);

    Hash pHash{3, 666013}, tHash {3, 666013};
    Hash oHash{3, 666013}, qHash {3, 666013};
    pHash.init(p, n);
    tHash.init(t, n);
    oHash.init(p, n);
    qHash.init(t, n);


    if(pHash.hash == tHash.hash && oHash.hash == qHash.hash)
    {
        v[++ nr] = 0;
    }

    for(int i = n; i < m; i ++)
    {
        tHash.roll(t[i - n], t[i]);
        qHash.roll(t[i - n], t[i]);
        if(pHash.hash == tHash.hash && oHash.hash == qHash.hash)
        {
            if(nr <= 1000)
                v[++ nr] = i - n + 1;
            else
                nr ++;
        }
    }
    g << nr << '\n';

    if(nr > 1000)
        nr = 1000;


    for(int i = 1; i <= nr; i ++)
        g << v[i] << ' ';

    return 0;
}