Cod sursa(job #2284403)

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

using namespace std;

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

struct Hash
{
    int 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()
{
    char p[100], t[100], n, m;
    int nr = 0, v[1000], k = 0;
    f >> p >> t;
    n = strlen(p);
    m = strlen(t);

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

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

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


    return 0;
}