Cod sursa(job #2284557)

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

using namespace std;

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

char p[2000005], t[2000005], n, m;
long long nr, v[1005];

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

    void init (char *s, long long  len)
    {
        power = 1, hash = 0;
        for(long long i = len - 1; i >= 0; --i)
        {
            hash = (hash + (1LL * power * s[i]) % m) % 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{31,40099}, tHash {31,40099};
    Hash oHash{53,319993}, qHash {53,319993};
    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(long long 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(long long i = 1; i <= nr; i ++)
        g << v[i] << ' ';

    return 0;
}