Cod sursa(job #2284482)

Utilizator m0rsCiacu Cristian m0rs Data 17 noiembrie 2018 11:12:18
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <cstring>
#include <fstream>

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

    void init(char *s, int len)
    {
        power=1,hash=1;

        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;
    }
};

using namespace std;

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

int main()
{
    char p[100], t[100];
    int n,m,nr=0,k=0,v[100];
    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)
    {
        cout<<" ";
        nr++;
    }

    for (int i=n;i<m;i++)
    {
        tHash.roll(t[i-n],t[i]);
        if (pHash.hash==tHash.hash)
        {
            v[k++]=i-n+1;
            nr++;
        }
    }
    cout<<nr<<"\n";
    for (int i=0;i<k;i++)
        cout<<v[i]<<" ";
    return 0;
}